一维状态压缩

解题思路:

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>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN=1e6;

int a[110][110],dp[110]; 

int main(){

int T,n; 

cin>>T;

while(T--){

cin>>n;

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

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

{

cin>>a[i][j];

}

}

for(int i=1;i<=n;++i) dp[i]=a[n][i];

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

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

dp[j]=max(dp[j],dp[j+1])+a[i][j];

}

}

cout<<dp[1]<<endl;

// cout<<ans<<endl;

}

return 0;

}