三角形 （C语言代码）

解题思路:


从后往前走


注意事项:





参考代码:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int a[150][150];

int dp[150][150];

int main()

{

    int n;

    int m;

    int i, j;

    scanf("%d", &m);

    while(m--)

    {

    scanf("%d",&n);

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

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

            scanf("%d", &a[i][j]);

        }

    }

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

        dp[n][i] = a[n][i];

    }

    for(i = n;i > 1;i--){

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

            if(dp[i][j] > dp[i][j+1]){

                dp[i-1][j] = a[i-1][j] + dp[i][j];

            }else {

                dp[i-1][j] = a[i-1][j] + dp[i][j+1];

            }

        }

    }

    printf("%d\n", dp[1][1]);

    }

    return 0;

}