三角形 简单dp练习

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int main(){
    // 定义变量n和t，分别表示测试用例的数量和每个测试用例的行数
    int n, t;
    // 定义dp数组，用于存储动态规划的结果
    int dp[105][105];
    // 定义v数组，用于存储输入的值
    int v[105][105];
    // 读取测试用例的数量
    cin >> n;
    // 循环处理每一个测试用例
    while(n--){
        // 读取当前测试用例的行数
        cin >> t;
        // 读取输入的值并存储到v数组中
        for(int i = 1; i <= t; i++){
            for(int j = 1; j <= i; j++){
                cin >> v[i][j];
            }
        }
        // 初始化dp数组的第一个元素
        dp[1][1] = v[1][1];
        // 使用动态规划计算最大路径和
        for(int i = 2; i <= t; i++){
            for(int j = 1; j <= i; j++){
                if(j > 1){
                    // 如果当前列不是第一列，取上方或左上方的最大值加上当前值
                    dp[i][j] = max(v[i][j] + dp[i-1][j], v[i][j] + dp[i-1][j-1]);
                } else {
                    // 如果当前列是第一列，只能取上方的值加上当前值
                    dp[i][j] = v[i][j] + dp[i-1][j];
                }
            }
        }
        // 找到dp数组最后一行的最大值
        int kkk = -1;
        for(int i = 1; i <= t; i++){
            kkk = max(kkk, dp[t][i]);
        }
        cout << kkk << endl;
    }
    return 0;
}