接触的第一道DP题，动态规划入门
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从 7→3→8→7→5 的路径产生了最大
输入格式
第一个行一个正整数r ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出格式
单独的一行,包含那个可能得到的最大的和。
30
什么是动归？
某度上是那么说的
动态规划是运筹学的一个分支，是求解决策过程最优化的过程。
总的来说，动态规划最大的特征也是前提条件也就是最优化原理和无后效性。
最优化原理就是指
在当前看来，这一选择策略是最佳选择。
无后效性就是指
以前各阶段的状态无法影响它未来的决策。
是不是还不太清楚？我们直接来看这道题吧。
题目分析
我们需要求出，数字三角形中，从第一层到最底层的中的一条路径，使得这条路径上的数字之和最大。
用 a[ i ][ j ] 来存储处于第 i 排第 j 个数字的值。
定义一个二维数组 dp ，使得 dp[ i ][ j ] 表示从第 i 层第 j 个数走到最下面一层所得到的最大的路径数之和。
拿样例来说:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
因为共五层，所以 dp[ 5 ][ j ] 的值就为 a[ 5 ][ j ]
dp[ 4 ][ 1 ] 即第四排第一个数2，表示的是2到第五排的最大的路径数之和，
dp[4][1] = a[4][1] + max(dp[5][1],dp[5][2]) = 2+5 = 7
dp[ 4 ][ 2 ] 即第四排第二个数7，表示的是7到第五排的最大的路径数之和，
dp[4][2] = a[4][2] + max(dp[5][2],dp[5][3]) = 7+5 = 12
dp[ 3 ][ 1 ] 即第三排第一个数8，表示的是8到第五排的最大的路径数之和，
dp[3][1] = a[3][1] + max(dp[4][1],dp[4][2]) = 8+12 =20
可以看出， dp[ i ][ j ] 的值取决于当前位置上数字的值，和下一层相邻两个数的 dp 值。
可以看到这里每一次更新dp的值时，都是遵循最优化原理的，且当前的过去的状态不会再因为现在的决策而改变。
所以当 i = { 1 , 2 , 3 , 4 } 时
dp[ i ][ j ] = a[ i ][ j ] + max( dp[ i+1 ][ j ],dp[ i+1 ][ j+1 ] )
我们把这样的式子称作动态规划的状态转移方程，在想要用到动态规划解决问题时，推出正确的状态转移方程非常重要。
动态规划能极大的提高效率。
上题也可以用 递归 或 dfs（深度优先搜索） 解决，但是这两种算法时间复杂度都较高，在数据范围大时，可能会超过时间限制。
但如果使用动归，时间复杂度只有O(n)=n^2。虽然不算最好，但也足够解决这一类竞赛题目了。
代码实现看这里
#include<iostream>
using namespace std;
int a[1005][1005],n;//注意数据范围
int dp[1005][1005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)//注意循环次数
cin>>a[i][j];//输入数字三角形每一位置的值
for(int i=n;i>=1;i--)//第n层dp值直接设为a的值
for(int j=1;j<=i;j++)//从第n-1层开始更新dp的值
dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);//状态转移方程
cout<<dp[1][1]<<endl;
return 0;
}
