动态规划题目

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 1e2 + 5;

int dp[N][N],a[N][N],maxy,n;

int main()

{

cin >> n;

for(int i = 1;i <= n;i ++)

{

for(int j = 1;j <= i;j ++)

{

cin >> a[i][j];//首先输入数组

}

}

for(int i = 1;i <= n;i ++)

{

for(int j = 1;j <= n;j ++)

{

dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + a[i][j];//这里不妨把上面的每一个值都加起来向下传递

}

}

maxy = dp[n][1];

for(int i = 2;i <= n;i ++)

{

maxy = max(maxy,dp[n][i]);

}

cout << maxy;

return 0;

}