题目如下：

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的： 

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 

 
已经告诉你了，这是个DP的题目，你能AC吗?

Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。 

Output

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。 

Sample Input

1
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Sample Output

30

递归代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define mm(a,n) memset(a,n,sizeof(a))
#define ll long long
using namespace std;
int a[1001][1001],n;
//求出二维数组坐标(x,y)的最大值。
int fun(int x,int y)
{
    if(x==n)return a[x][y];
    return  a[x][y]+max(fun(x+1,y),fun(x+1,y+1));
}
int main()
{
    int t;
//        freopen("C:\\Users\\nuoyanli\\Desktop\\acminput.txt","r",stdin);
//    freopen("C:\\Users\\nuoyanli\\Desktop\\acmoutput.txt","w",stdout);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=i; j++)
            {
                cin>>a[i][j];
            }
        }
        cout<<fun(1,1)<<endl;
    }
    return 0;
}

提交之后：

深度优先搜索

前面的递归算法，实际上是将整个数字三角形搜索了一遍，所以，完全可以用深度优先搜索算法。就是一条路走到黑，前面没有路就返回上一个路口，另选一条路走到黑…..如此反复，知道所有路全部走遍。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define mm(a,n) memset(a,n,sizeof(a))
#define ll long long
#define maxn 100
using namespace std;
int a[maxn][maxn],N,sum,Max;
void dfs(int i,int j)
{
    sum+=a[i][j];
    if(i==N)
    {
        if(sum>Max)
            Max=sum;
        return ;
    }
    for(int x=0; x<2; x++)
    {
        dfs(i+1,j+x);
        sum-=a[i+1][j+x];
    }
}
int main()
{
//    freopen("C:\\Users\\nuoyanli\\Desktop\\acminput.txt","r",stdin);
//    freopen("C:\\Users\\nuoyanli\\Desktop\\acmoutput.txt","w",stdout);
    int t;
    cin>>t;
    while(t--)
    {
        sum=0;
       Max=-0X3f3f3f;
        mm(a,0);
        cin>>N;
        for(int i=1; i<=N; i++)
            for(int j=1; j<=i; j++)
                cin>>a[i][j];
        dfs(1,1);
        cout<<Max<<endl;
    }
    return 0;
}

 运行结果：

记忆化搜索优化算法

运行上面的程序，可以发现运行速度是很慢的，这是因为在运行过程中，很多值被反复地计算。其实如果把已经计算出来的值保存起来，下次 用的时候直接那来算，速度会快上很多。这就是所谓的记忆化搜索。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define mm(a,n) memset(a,n,sizeof(a))
#define ll long long
#define maxn 100
using namespace std;
int a[maxn][maxn],N,total,dp[maxn][maxn];
int fun(int i,int j)
{
    if(i==N-1)
        return a[i][j];
    if(dp[i][j])
        return dp[i][j];
    dp[i][j]=a[i][j]+max(fun(i+1,j),fun(i+1,j+1));
    return dp[i][j];
}
int main()
{
    int t;
//            freopen("C:\\Users\\nuoyanli\\Desktop\\acminput.txt","r",stdin);
//    freopen("C:\\Users\\nuoyanli\\Desktop\\acmoutput.txt","w",stdout);
    cin>>t;
    while(t--)
    {
        mm(dp,0);
        cin>>N;
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<=i; j++)
            {
                cin>>a[i][j];
            }
        }
        cout<<fun(0,0)<<endl;
    }
    return 0;
}

运行结果：

简单dp： 

思路： 
 

这里写图片描述

代码如下：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define mm(a) memset(a,0,sizeof(a))
#define ll long long
ll dp[105][105];
int main()
{
    int t;
//	            freopen("C:\\Users\\nuoyanli\\Desktop\\acminput.txt","r",stdin);
//    freopen("C:\\Users\\nuoyanli\\Desktop\\acmoutput.txt","w",stdout);
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        mm(dp);
        for(int i = 0; i < n; i++)
            for(int j = 0; j <= i; j++)
                cin>>dp[i][j];
        for(int i = n - 1; i > 0; i--)
            for(int j = n - 1; j > 0; j--)
                dp[i - 1][j - 1] += max(dp[i][j],dp[i][j - 1]);
        cout<<dp[0][0]<<endl;
    }
    return 0;
}

 运行结果：

在此另外附上可能有利于初学者理解动态规划的篇章：https://blog.csdn.net/nuoyanli/article/details/86134825，希望对读者有所帮助。（由于笔者技术有限如有错误欢迎评论区指正）