Path in Matrix

Task: Find the maximum path sum from given N*N matrix, Start from any column in row 0, move in three paths from current position Matrix[r][c] to Matrix[r+1][c] or Matrix[r+1][c-1] or Matrix[r+1][c+1] up to row N-1. 

Example:

Input:

1

2 

348 391 618 193 

Output:

1009 // 391 + 618 

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. using namespace std;
3. int main()
4.  {
5. int t;
6. cin>>t;
7. while(t--)
8. {
9.     int n;
10.     cin>>n;
11.     int a[n][n];
12.     for(int i=0;i<n;i++)
13.     {
14.         for(int j=0;j<n;j++)
15.         {
16.             cin>>a[i][j];
17.         }
18.     }
19.     int dp[n][n];
20.     for(int i=0;i<n;i++)
21.     {
22.         dp[0][i]=a[0][i];
23.     }
24.     for(int i=1;i<n;i++)
25.     {
26.         for(int j=0;j<n;j++)
27.         {
28.             if(j==0)
29.             {
30.                 dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j+1]);
31.             }
32.             else if(j==n-1)
33.             {
34.                 dp[i][j]=a[i][j]+max(dp[i-1][j-1],dp[i-1][j]);
35.             }
36.             else
37.             {
38.                 int t = max(dp[i-1][j-1],dp[i-1][j]);
39.                 dp[i][j]=a[i][j]+max(t,dp[i-1][j+1]);
40.             }
41.         }
42.     }
43.     int max=dp[n-1][0];
44.     for(int i=0;i<n;i++)
45.     {
46.         if(max<dp[n-1][i])
47.         {
48.             max=dp[n-1][i];
49.         }
50.     }
51.     cout<<max<<endl;
52. }
53. return 0;
54. }
55. // Updated Version
56. class Solution{
57. public:
58.     int maximumPath(int N, vector<vector<int>> a)
59.     {
60.         // code here
61.         int dp[N][N];
62.     for(int i=0;i<N;i++)
63.     {
64.         dp[0][i]=a[0][i];
65.     }
66.     for(int i=1;i<N;i++)
67.     {
68.         for(int j=0;j<N;j++)
69.         {
70.             if(j==0)
71.             {
72.                 dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j+1]);
73.             }
74.             else if(j==N-1)
75.             {
76.                 dp[i][j]=a[i][j]+max(dp[i-1][j-1],dp[i-1][j]);
77.             }
78.             else
79.             {
80.                 int t = max(dp[i-1][j-1],dp[i-1][j]);
81.                 dp[i][j]=a[i][j]+max(t,dp[i-1][j+1]);
82.             }
83.         }
84.     }
85.     int max=dp[N-1][0];
86.     for(int i=0;i<N;i++)
87.     {
88.         if(max<dp[N-1][i])
89.         {
90.             max=dp[N-1][i];
91.         }
92.     }
93.     return max;
94.     }
95. };

---

Here is the Video: