給定一個由n行數(shù)字組成的數(shù)字三角形，設(shè)計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。
輸入數(shù)據(jù)a[m][n]：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
最優(yōu)解數(shù)組b[m][n]：

分析：

分析：
　　這是一道典型的動態(tài)規(guī)劃問題，求頂?shù)降椎囊粭l路徑數(shù)字總和最大，按照動態(tài)規(guī)劃思想，從底往上，子問題的和大，那么父問題的和就大，所以在給數(shù)組打底子的時候，就要找大的
1、二位數(shù)組代表什么：b[i][j]代表從這個點一直走到最后的最大值
2、數(shù)組打底：b數(shù)組把n-1行填充起來
3、遞推式：根據(jù)題目可知，要從n-2行往0行遍歷，也就是從下往上。公式為：b[m][n]=max{ b[m+1][n]+a[m][n] , b[m+1][n+1]+a[m][n] }

#include<stdio.h>
#define n 5           //行數(shù) 

int main(){
    int **a=new int*[n];  //接收輸入的數(shù)據(jù) 
    int **b=new int*[n];  //存放最優(yōu)值，b[i][j]存放著a[i][j]到底端的最大路徑的和 
    for(int i=0;i<n;i++){
        a[i]=new int[n];
        b[i]=new int[n];
    } 
    for(int i=0;i<n;i++){          
        for(int j=0;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<n;i++)     //數(shù)組打底工作
        b[n-1][i]=a[n-1][i];
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<=i;j++){
    b[i][j]=(b[i+1][j]+a[i][j])>(b[i+1][j+1]+a[i][j])?(b[i+1][j]+a[i][j]):(b[i+1][j+1]+a[i][j]);
        }
    }
    printf("%d\n",b[0][0]);
    return 0;
} 

運行截圖