三角形-题解（递推求解）

解题思路:

1、自下而上求解（自上而下求解很难搞，用递归很容易超时）。

2、注意状态转移方程：dp[t][t1]=dp[t][t1]+Max(dp[t+1][t1+1],dp[t][t1]),这个方程后面会详讲。

注意事项:

这道题应该写错了，应该是向下或向右下，例题好像也有问题

一看到这题我一开始就是暴力从上向下递归，后面发现基本都会超时。

可能会有不少人不理解为什么要自下向上查找，很重要的一个原因就是从下向上查找最后只会到一个点上———顶点，也就是最上面的点上。

如果从上往下查找的话就只能用递归了（递推不行，递推不到最优解），这里我还没想到如何优化，估计是用数组记数，减少递归计算次数进行优化，这个大家可以去试试。

自上向下查找用递推是求不出最优解的，比如举个例子

1/*第一层*/

2 3

5 4 3

7 8 9 12/*第四层*/

看这个，自上往下应该先后是1,3,4,9，一共是17。

但实际答案应该是1,3,3,12，一共是19。

dp[t][t1]=dp[t][t1]+Max(dp[t+1][t1+1],dp[t][t1])

从下开始查找最大值，因为始终所有线路会汇聚到一起，所以总的最大可以转化为：

（第一层+第二层+第三层+第四层+...最后一层）=（第一层+第二层+第三层+....+倒数第二层到最后一层的最大值）=（第一层+第二层+第三层+...+倒数第三层到最后一层的最大值）

如此递推下去就能找到最大值

参考代码:

#include <iostream>
using namespace std;
int Max(int a,int b); 
int main()
{
    int dp[100][100],num,x,t=0,t1=0;
    cin>>num;
    while (num--)
    {
        cin>>x;
        for (;t<x;t++)
        {
            for (t1=0;t1<=t;t1++)
            cin>>dp[t][t1];
        }    

        for (t=x-2;t>=0;t--)/*换层循环，层数向上增加*/
        {
            for (t1=0;t1<=t;t1++)/*每一行求最优*/
            dp[t][t1]=dp[t][t1]+Max(dp[t+1][t1+1],dp[t+1][t1]);/*从下向上开始查找，逐步找最优解*/
        }
        t=0;
        t1=1;
        cout<<dp[0][0]<<endl;
    }
    return 0;
}
int Max(int a,int b)
{
    return a>b?a:b;
}