在进行动态规划的时候需要注意：
1、求出状态转移方程。
2、要避免出现低效率的递归。可以用数组进行保存，实现记忆化查找。
3、需要有一个出口（边界），否则会陷入死循环。
例：杭电2084数塔
题意：求出从第一个点只能走相邻节点的最大值。
分析：每个点的最大值由它下面的两个节点决定，可以得到状态转化方程。
a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1])
#include<iostream>
#include<math.h>
#include<algorithm>
#include<memory.h>
using namespace std;
int main()
{
int c;
cin>>c;
while(c--)
{
int row;
cin>>row;
int a[105][105];
memset(a,0,sizeof(a));
for(int i=1;i<=row;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
for(int i=row;i>=1;i--)
{
for(int j=i;j>=1;j--)
{
a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]); //状态转移方程
}
}
cout<<a[1][1]<<endl;
}
}
类似的题目还有最长公共子序列、最长上升子序列等等。
