概念

多阶段决策问题：对于某一类活动，可以分为若干个相互联系的阶段，每个阶段都需要做出决策，采取一定的措施，这个阶段的决策确定之后，会影响到下一个阶段。每一个阶段的决策构成了一个决策序列，称为策略。每个阶段都有几个决策可以选择，从而就有很多个策略可以选择，在所有可以选择的策略中选取一个最优的策略，可以达到我们预定的效果。动态规划就是解决多阶段决策问题最优的通用方法。

利用最短路径问题理解多阶段决策

在上图中，如果想求A到E的最短路径，在这个过程中，涉及了A——>B、B——>C、C——>D、D——>E这几个阶段，在每个阶段中，又有多种决策(权值不同)，前一个决策的结果会影响后面的决策，但是后面的决策不会反过来影响前面的决策。
下面是多种不同的策略，使用一定的方法从其中选择出最优的策略，计算出A、E之间的最短路径，就是动态规划算法可以解决的事情。

• A——>B1——>C1——>D1——>E
• A——>B1——>C2——>D1——>E
• A——>B2——>C3——>D2——>E
• A——>B2——>C3——>D3——>E
• … …

数塔问题(原题链接)

题目描述

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

输入

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

输出

从底层走到顶层经过的数字的最大和是多少？

样例输入

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

样例输出

30

解题思路：数塔一共有5层，顶层为第一层，底层为第五层。若想从第五层走到第一层，经过的数字之和最大，需要保证在到达第二层的时候，经过的数字之和最大。即如果需要在某个点使得数字之和最大，那么需要在到达这个点之前使得数字之和最大，最后加上这个点的数字即可。

同理，若想在到达第二层的时候经过的数字之和最大，那么需要在到达第三层的时候，经过的数字之和最大… …以此类推。通过分析可以得到，当前点只可以由其正下方和右下方的点到达，设dp[i][i]表示走到第i行第j列的时候，经过的数字之和的最大值，那么可以得到状态转移方程：

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

最后，dp[1][1]表示从第五层走到第一层，所经过的数字之和的最大值。
AC代码1 —— 动态规划：

#include <iostream>

using namespace std;
const int N = 110;
int dp[N][N],a[N][N],n;

int main()
{
    
    scanf("%d",&n);
    for (int i = 1; i <= n;i++)
        for (int j = 1;j <= i;j++)
            scanf("%d",&a[i][j]);//读入数据
            
    //初始化dp数组,最后一层不需要状态转移
    for (int i = 1;i <= n;i++) dp[n][i] = a[n][i];
    
    //从倒数第二层开始状态转移
    for (int i = n - 1;i >= 1;i--)//枚举行
        for (int j = 1;j <= n;j++)//枚举列
            dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + a[i][j];//状态转移方程
    cout << dp[1][1] << endl;
    return 0;
}

参考代码2 —— DFS：尝试深度优先搜索，直接暴力搜索所有路径，记录最大值即可。另外，本题的本质是寻找一条路径，使得这条路径上的数字之和最大，故不管是从顶到底，还是从底到顶，最终的结果应该是一样的。根据以上分析，可以从a[1][1]开始搜索最大和。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int a[N][N],n;
int maxn,sum;//maxn存储最后的结果

int dfs(int x,int y,int sum)
{
    
    //dfs函数中第三个参数用来更新最大值
    maxn = max(maxn,sum);
    if (x + 1 <= n)//不能超过边界
    {
    
        dfs(x + 1,y,sum + a[x + 1][y]);//搜索正下方
        dfs(x + 1,y + 1,sum + a[x + 1][y + 1]);//搜索右下方
    }
}

int main()
{
    
    scanf("%d",&n);
    for (int i = 1; i <= n;i++)
        for (int j = 1;j <= i;j++)
            scanf("%d",&a[i][j]);//读入数据
            
    dfs(1,1,a[1][1]);//从第一行第一列开始搜索,初始最大值为a[1][1]
    
    cout << maxn << endl;
    return 0;
}