DP动态规划解三角最大路径(动态规划学习之一)

题：

图示出了一个数字三角形，请编一个程序，
计算从顶至底的某处的一条路劲，
使该路劲所经过的数字的总和最大。

图如下：

    7

   3  8

  8  1  0

 2  7  4  4

4  5  2  6  5
（1） 每一步可沿左斜线向下或右斜线向下；
（2） 1＜三角形行数≤100；
（3） 三角形中的数字为0，1，……99。
输入数据：
由INPUT.TXT文件中首先读到的是三角形的行数，
在例子中INPUT.TXT表示如图。

输入：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 

解题：

这个题用DP解是最为方便的，假定M(i,j)为第i层上第j个点的最大路径点，那么M(i,j)=max(M(i+1,j),M(i+1,j+1))+B(i,j);其中i层次从上到下递增，B(i,j)为三角在i,j位置的值。这样这个大问题就可以划归一些小的可重复的问题来求解，另外还有一点，就是，其中有重复求解地方，例如，计算M(1,0)是计算一次M(2,1),计算M(1,1)时又计算一次M(2,1)，这样符合动态规划求解的2个特征：

[1]最优子结构;[2]子问题的重叠性;

这里我们用一个数组结构来记录每次的状态，避免重复计算

详细代码如下：

 

#include "iostream"
#include "fstream"
#include "vector"
using namespace std;
int tri[100][100];
int tri_max[100][100];
int tri_col[100];
int layer; //the layer of the trigle

int maxpath(int i,int j)
{
        if(i == layer) return 0; //the last layer is layer+1 and the value is 0

        if(tri_max[i][j] == -1)
        {
                int max1=maxpath(i+1,j);
                int max2=maxpath(i+1,j+1);
                if(max1 > max2)
                {
                        tri_max[i][j]=max1+tri[i][j];
                        tri_col[i+1]=j;
                }else{
                        tri_max[i][j]=max2+tri[i][j];
                        tri_col[i+1]=j+1;
                }
        }
        return tri_max[i][j];
}
int main()
{
        ifstream fin("trigle.txt");
        fin>>layer;
// cout<
        int i,j;
        //initial max trigle

        for(i=0;i<100;i++)
                for(j=0;j<100;j++)
                        tri_max[i][j] = -1;
        for(i=0;i<layer;i++)
        {
                for(j=0;j<i+1;j++)
                {
                        fin>>tri[i][j];
                }
        }
        int sum = maxpath(0,0);
        cout<<"the sum of max path is:"<<sum<<endl;
        cout<<"the column of the path is :";
        for(i=0;i<layer;i++)
        {
                cout<<tri_col[i]+1<<"->";
        }
}