动态规划 路径问题

解题思路:

注意事项:

参考代码:#include <iostream>
using namespace std;

int main(){
    int T,N,A[100][100],B[100][100]={0};
    cin>>T;
    for (int t=0;t<T;t++){
        cin>>N;
        for (int i=0;i<N;i++){
            for (int j=0;j<=i;j++){
                cin>>A[i][j];
            }
        }
        B[0][0]=A[0][0];
        for (int i=1;i<N;i++){
            B[i][0]=B[i-1][0]+A[i][0];
            B[i][i]=B[i-1][i-1]+A[i][i];
        }
        for (int i=1;i<N;i++){
            for (int j=1;j<i;j++){
                if (B[i-1][j-1]>B[i-1][j]){
                    B[i][j]=A[i][j]+B[i-1][j-1];
                }else{
                    B[i][j]=A[i][j]+B[i-1][j];
                }
            }
        }
        int max=0;
        for (int i=0;i<N;i++){
            if (max<B[N-1][i]){
                max=B[N-1][i];
            }
        }
        cout<<max<<endl;
    }
    return 0;
}