题目 1177: 三角形（动态规划）

解题思路:题目可能有问题，每一步只能由当前位置向左下或右下，而是每一步只能由当前位置向正下下或右下。

注意事项:因此可以写出动态规划的函数：dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j];

参考代码:

#include <bits/stdc++.h>

using namespace std;

int dp[101][101];

int main() {

int T, n , a[101][101], maxn;

cin >> T;

for (int k = 0; k < T; k++) {

cin>>n;

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

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

cin>>a[i][j];

}

}

dp[1][1] = a[1][1];

maxn = -1;

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

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

dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j];

}

}

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

if(dp[n][i]>maxn)

maxn=dp[n][i];

}

cout << maxn << endl;

return 0;

}