动态规划（入门篇）

什么是动态规划问题？

通过金矿故事我们可以了解到动态规划问题是一种用来解决一类最优化问题的算法思想，就是将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原来问题的最优解。

解决动态规划问题的核心在于：找到重复子问题，记住之前做的事

如何理解动态规划中的概念？

重叠子问题

如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有“重叠子问题”，动态规划通过记录重叠子问题的解，来使下次碰到相同的子问题时直接使用之前记录的结果，依次避免大量重复计算。因此，一个问题必须拥有重叠子问题，才能使用动态规划去解决

我们从熟悉的斐波那契数列来理解重叠子问题

初学者在接触斐波那契数列的时候，可能一般的写法是这样的：

int F(int n){
  if(n == 0 || n == 1) return 1;
  else return F(n - 1) + F(n - 2);
}

这里就是不断地分解问题为子问题 ==> 动态规划问题必须要满足

然而实际上，这个递归会涉及到很多重复的计算。

当n = 5的时候，可以得到F(5) = F(4) + F(3)，接下来在计算F(4)的时候，又会有F(4) = F(3) + F(2)，这个时候我发现F(3)被重复计算，可以推知，如果n非常大，重复计算的次数将难以想象，实际复杂度会达到O(2ⁿ)

为了避免重复计算，我们可以开辟一个一维数组dp，保存已经计算过的结果，用dp[n]记录F(n)的结果，并用dp[n] = -1 表示当前还没有被计算过 ==> 就是我们说的做备忘录，记住之前做的事

int dp[MAXN];

int F(int n){
  if(n == 0 || n == 1) return 1;		// 递归边界
  if(dp[n] != -1) return dp[n];			// 已经计算过，直接返回结果
  else{
    dp[n] = F(n - 1) + F(n - 2);
    return dp[n];
  }
}

最优子结构

我们通过数塔问题来理解"最优子结构"这个概念

其中第一层有一个数字，第二层有两个数字······第n层有n个数字，现在从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问：最后路径上所有数字相加后得到的和最大是多少？

如果按照题目描述，我们可以用二维数组f，其中f[i][j] 存放第i层的第j个数字，那么 f[1][1] = 5,f[2][1] = 8 ··· f[5][5] = 4此时，如果我们尝试穷举所有路径，然后记录路径上数字和的最大值，那么由于每层中每个数字都有两个分支，时间复杂度为O(2 ⁿ)，这样的时间复杂度显然是我们不可以接受的

基于上面的考虑，我们不妨令dp[i][j] 表示从第i行第j个数字出发的到达最底层所有路径中能得到的最大和

我们可以归纳得到一个信息：如果要求出dp[i][j] ，那么一定要先求出它的两个子问题，从位置(i + 1, j)到达最底层的最大和dp[i + 1][j] 和位置(i + 1,j + 1)到达最底层的最大和dp[i + 1][j + 1] ，即进行一次决策

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

dp[i][j]称为问题的状态，上面的式子称为状态转移方程

我们可以发现，状态dp[i][j]只与第i + 1层状态有关，而与其他层状态无关，那么这样的转移什么时候能够结束呢？我们可以发现在数塔的最后一层的dp值总是等于元素本身

这样就可以从最底层各位置的dp值开始，不断地往上求出每一层各位置的dp值，最后就会得到我们想要的dp[1][1]

分析到这里，我们的问题基本得到解决，在这个过程中我们发现解决问题的关键在找到状态转移的方程，如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构

一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划，

子问题独立

想一想上面数塔问题中，我们在分解成重叠子问题的时候，状态dp[i][j]只与第i + 1层状态有关，而与其他层状态无关，这里就是子问题独立

边界

当我们找到数塔问题的状态转移方程，那么这样的转移什么时候能够结束呢？我们可以发现在数塔的最后一层的dp值总是等于元素本身，在这个时候就可以进行返回了，这里就是我们所说的边界

如何解决动态规划问题？

当我们理解了动态规划中的一些重要概念以后，解决动态规划问题可以按下面的步骤去思考

构造问题所对应的过程
思考过程的最后一个步骤，看看有哪些选择情况
找到最后一步的子问题，确保符合**“子问题重叠”，把子问题中不相同的地方设置为参数**
使得子问题符合“最优子结构”
找到边界，考虑边界的各种处理方式
确保满足“子问题独立”，一般而言，如果我们是在多个子问题中选择一个作为实施方案，而不会同时实施多个方案，那么子问题就是独立的
考虑如何做备忘录
分析所需时间是否满足要求
写出转移方程式

我们再进一步提炼，得到解题中最为重要的四步法

问题拆解，找到问题之间的具体联系

状态定义

递推方程推导

实现

我们按照这四个步骤来实现数塔问题

问题拆解

这里的总问题是求出最大的路径和，路径是这里的分析重点，路径是由一个个元素组成的，[i][j] 位置的元素，经过这个元素的路径肯定也会经过 [i - 1][j] 或者 [i - 1][j - 1]，因此经过一个元素的路径和可以通过这个元素上面的一个或者两个元素的路径和得到。

也就是我们要求得[1][1]位置元素一定会经过[2][1]或者[2][2]，这样每一步递推下去，我们就会得到最终最大的路径和。

状态定义

状态的定义一般会和问题需要求解的答案联系在一起，这里其实有两种方式，一种是考虑路径从上到下，另外一种是考虑路径从下到上，因为元素的值是不变的，所以路径的方向不同也不会影响最后求得的路径和，如果是从上到下，你会发现，在考虑下面元素的时候，起始元素的路径只会从[i - 1][j] 获得，每行当中的最后一个元素的路径只会从 [i - 1][j - 1] 获得，中间二者都可，这样不太好实现，因此这里考虑从下到上的方式，状态的定义就变成了 “最后一行元素到当前元素的最大路径和”，对于 [0][0] 这个元素来说，最后状态表示的就是我们的最终答案。

递推方程

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

实现

这里初始化时，我们需要将最后一行的元素填入状态数组中，然后就是按照前面分析的策略，从下到上计算即可

/*
 * @Author: Rick
 * @Email: Kay_Rick@outlook.com
 * @Date: 2020-02-23 20:23:31
 * @Last Modified by: Rick
 * @Last Modified time: 2020-02-23 20:41:05
 * @Description: 动态规划 数塔问题
 */
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1000;
int f[maxn][maxn], dp[maxn][maxn];

int main(void){
    int n;  // 层数
    scanf("%d", &n);
    // 输入数塔
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            scanf("%d", &f[i][j]);
        }
    }
    // 最后一行元素填入状态数组 ==> 边界
    for (int k = 1; k <= n; k++)
    {
        dp[n][k] = f[n][k];
    }
    // 从第n-1层不断往上计算出dp[i][j]
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = 1; j <= i; j++)
        {
            // 状态转移方程
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
        }
    }
    printf("%d\n", dp[1][1]);
    return 0;
}

输入：

输出：