Advertisement
Josif_tepe

Untitled

Dec 14th, 2021
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int n;
  5. int mat[105][105];
  6. int dp[105][105];
  7. int rek(int i, int j)
  8. {
  9.     if (i==(n-1))
  10.     {
  11.         return mat[i][j];
  12.     }
  13.     if(dp[i][j]!=-1)
  14.     {
  15.         return dp[i][j];
  16.     }
  17.     int zbir=-2e9;
  18.  
  19.     if(i+1<n)
  20.     {
  21.        zbir=max(zbir,rek(i+1,j)+mat[i][j]);
  22.     }
  23.     if(j+1<n && i+1<n)
  24.     {
  25.        zbir=max(zbir,rek(i+1,j+1)+mat[i][j]);
  26.     }
  27.     dp[i][j]=zbir;
  28.     return zbir;
  29.  
  30. }
  31. int main()
  32. {
  33.     cin>>n;
  34.     for(int i=0;i<n;i++)
  35.     {
  36.         for(int j=0;j<(i+1);j++)
  37.         {
  38.             cin>>mat[i][j];
  39.         }
  40.     }
  41.     for(int i=0;i<n;i++)
  42.     {
  43.         for(int j=0;j<(i+1);j++)
  44.         {
  45.             dp[i][j]=-1;
  46.         }
  47.     }
  48.     cout << rek(0, 0) << endl;
  49.     return 0;
  50. }
  51.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement