简单的DP算法--数塔

在进行动态规划的时候需要注意：
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;


    }
}

类似的题目还有最长公共子序列、最长上升子序列等等。