（dp）数字三角形

题目

数字三角形问题。有一个由非负整数组成的三角形，第一行只有一个数，除了最下行 之外每个数的左下方和右下方各有一个数
从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数 全部加起来。如何走才能使得这个和尽量大？

具体实现代码中的d我们用maxsum表示
最初的位置我们用d存

1.把当前的位置(i, j)看成一个状态 ，然后定义状态(i, j)的指标函数d(i, j)为从格子(i, j)出发时能得到的最大和 （包括格子(i, j)本身的值）。在这个状态定义下，原问题的解是d(1, 1)。
2.不同状态之间是如何转移的。从格子(i, j)出发有两种决策。如果往左走，则走 到(i＋1, j)后需要求“从(i＋1, j)出发后能得到的最大和”这一问题，即d(i＋1, j)。类似地，往右走之后需要求解d(i＋ 1 , j＋1)。由于可以在这两个决策中*选择，所以应选择d(i＋1,j) 和d(i＋1,j＋1)中较大的一个。
3.状态转移方程：d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}
4.如果往左走，那么最好情况等于(i, j)格子里的值a(i, j)与“从(i＋1, j)出发的最大总和”之 和，注意这里的“最大”二字。如果连“从(i＋1,j)出发走到底部”这部分的和都不是最大 的，加上a(i, j)之后肯定也不是最大的。这个性质称为最优子结构（optimal substructure）， 也可以描述成“全局最优解包含局部最优解”。
5.状态和状态转移方程一起完整地描 述了具体的算法。

方案1：递归

可以用记忆化搜索的方法计算状 态转移方程。当采用记忆化搜索时，不必事先确 定各状态的计算顺序，但需要记录每个状态“是 否已经计算过”。
题目中说各个数都是非 负的，因此如果已经计算过某个d[i][j]，则它应是非负的。这样，只需把所有d初始化为－ 1，即可通过判断是否d[i][j]！=-1得知它是否已经被计算过。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxx 101
int d [maxx][maxx];
int n;
int maxsum[maxx][maxx];
int ms(int i,int j); 
int main()
{
    int i,j;
    cin>>n;
    for(i=1;i<=n;++i)
        for(j=1;j<=i;++j)
        {
            cin>>d[i][j];
            maxsum[i][j]=-1;
        }
    cout<<ms(1,1)<<endl;
 } 

int ms(int i,int j)
{
    if(maxsum[i][j]!=-1)
    return maxsum[i][j];
    //保存算过的 赋值语句本身有返回值”的规定，
    //可以把maxsum[i][j]的工作合并到函数的返回语句中。

    if(i==n)
    maxsum[i][j]=d[i][j];
    else {
        int y=ms(i+1,j+1);
        int x=ms(i+1,j);
        maxsum[i][j]=max(x,y)+d[i][j];
    }
    return maxsum[i][j];
}

方案二：递推

i是 逆序枚举 的，因此在计算d[i][j]前，它所需要的d[i＋1][j]和d[i＋1][j＋1]一定已经计算出来了。

最底下的元素d（i，j）的maxsum[i][j]一定是他自身
这样我们可以自下而上地推出每一个d（i，j）的maxsum

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxx 101
int d [maxx][maxx];
int n;
int maxsum[maxx][maxx];

int main()
{
    int i,j;
    cin>>n;
    for(i=1;i<=n;++i)
        for(j=1;j<=i;++j)
        {
            cin>>d[i][j];
        }
    for(i=1;i<=n;++i)
        maxsum[n][i]=d[n][i];
    for(i=n-1;i>=1;--i)
        for(j=1;j<=i;++j)
            maxsum[i][j]=max(maxsum[i+1][j],maxsum[i+1][j+1])+d[i][j];
    cout<<maxsum[1][1]<<endl;

 } 

用一维数组存：

//直接用d的第n行代替
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxx 101
int d [maxx][maxx];
int n;
int  *maxsum;

int main()
{
    int i,j;
    cin>>n;
    for(i=1;i<=n;++i)
        for(j=1;j<=i;++j)
        {
            cin>>d[i][j];
        }
    maxsum=d[n];
    for(i=n-1;i>=1;--i)
        for(j=1;j<=i;++j)
            maxsum[j]=max(maxsum[j],maxsum[j+1])+d[i][j];
    cout<<maxsum[1]<<endl;

 }