动态规划 – Introduction

动态规划问题性质

最优子结构

一个最优化策略的子策略总是最优的,反过来,我们可以通过最优的子策略,推出最优策略。

无后效性

当我们通过一系列策略到达了某一阶段的某一状态时,下一步决策不受之前的一系列策略影响,仅由当前状态决定。

子问题重叠

算法计算的过程中会反复地求解相同的一定量的子问题,而不是不断生成没有见过的新问题。也就是说子问题空间不大,或是状态空间不大,我们可以通过存储状态的答案加快计算速度。

经典数塔问题

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

数塔问题

首先考虑上一节所说的状态表示与转移,我们先找一组符合动态规划要求性质的表示与转移:

  • 阶段:数塔的每一层就是一个阶段,转移的时候,从上一层向下一层转移。
  • 状态:位于数塔每一层的那个节点就是状态,因为每一步只能走到相邻的节点,所以状态决定了能够向下一阶段的哪些状态转移。
  • 状态转移:由题目中 每一步只能走到相邻的结点 得到,状态转移就是上一层节点向下一层相邻节点转移。
  • 初始状态:由题目中得到,数塔顶部节点。

如此,我们的可以由阶段和状态得到:

  • 状态表示:dp[i][j] 表示位于第 i 层第 j 个元素的最大数字之和。
  • 状态转移即为 dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + v[i][j]
  • 初始状态为 dp[1][1] = 9

动态规划题目特点

动态规划原本是用来解决求最值这类的最优化问题的,后人将其原理直接应用于计数存在性判定(本质上也是计数)一类的问题也能够 work,所以如果你看到最值、计数、存在性判定这三类问题,不妨思考一下使用动态规划来解决。

再看数塔问题,同样要求从顶层走到底层,若每一步只能走到相邻的结点,最值就是求走出一条路径的最大数字和是多少,计数可以是求走出一条路径数字和不超过 55 的方案数,存在性判定可以是求是否存在一条路径的数字和等于 55。

动态规划代码实现

两种写代码的方式:记忆化搜索递推。记忆化搜索是一种相对容易理解好上手的代码方式,递推需要考虑更多的东西,优点是支持加入各种高级优化。

先说记忆化搜索,这是一个相对简单的动态规划实现方法。它可以理解为在我们确定的状态上进行搜索,然后通过一个额外的数组保存每一个状态的答案,搜索某一个状态时,如果答案计算过就直接返回,否则继续向下搜索并保存计算过的答案!所以,点了搜索技能点的同学可以快速转型到记忆化搜索,它的好处有以下几点:

  • 能避免计算一些根本用不到的状态。
  • 决策边界容易考虑,搜不下去就是边界。
  • 减少思考量,不用考虑状态之间的计算顺序,程序只需要立足当前状态与当前状态的子状态即可。
  • 实现容易,写出搜索,加个记忆化就完事了。
  • 可以使用搜索的奇技淫巧优化。

因为记忆化搜索存在一个搜索的框架,所以可以写出一个比较抽象的模板:

int dp[状态表示];
int dfs(状态表示) {
    if (决策边界) return 决策边界答案; // 决策边界
    if (dp[状态表示] != 无效数值) return dp[状态表示]; // 记忆化
    for (当前状态表示的 子状态) dfs(子状态) 更新 dp[状态表示]; // 状态转移
    return dp[状态表示];
}
int solve() {
    memset(dp, 无效数值, sizeof(dp));
    return dfs(原问题状态);
}

再讲递推,简单了说是使用 For 循环嵌套对所有状态进行枚举,使用转移方程更新状态。

这里枚举状态的顺序就有讲究了,比如我们更新状态 A,需要状态 B、C、D 的答案,那么状态 B、C、D 肯定要先于状态 A 被我们枚举到,换句话说,确定状态 A 的时候,状态 B、C、D 必须已经被确定完了。一般来说,我们按照阶段地顺序枚举状态就可以了,但是很多时候问题情况比较复杂,按照阶段未必时最简单最容易实现的方法,所以枚举状态的顺序需要仔细思考。虽然,递推的实现方法相对记忆化搜索困难,但是他也有优点:

  • 可以加入各种动态规划优化。
  • 没有记忆化搜索中系统栈的开销,速度较快。

解决动态规划问题总结

说了这么多,动态规划的核心就是状态表示,我们要确定一个既不是那么复杂导致超时,又不过于简单产生后效性的合理状态表示。有了一个合理的状态表示之后,转移方程、决策边界和代码实现都是稍加思考就能得到了。

  • Step 1 确定状态表示,包含阶段划分与状态表示。
  • Step 2 写出转移方程:帮助你想清楚状态之间到底是如何转移的。
  • Step 3 确定边界:初始 Cases!
  • Step 4 如果使用递推,考虑一下状态枚举的顺序。

另外,一件重要的事情是:想清楚了再写代码、想清楚了再写代码、想清楚了再写代码!

做道例题:64. 最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明: 每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

先确定状态表示,这道题目里的阶段比较隐式,它是斜过来在对角线上的元素。想想为什么,阶段 1 是从距离起点 0 步的位置,阶段 2 是距离起点 1 步的位置……我们总是从上一个阶段的状态向下一个阶段的状态进行更新。

最小路径和阶段

那么,在每一个阶段中,我们需要知道它的具体位置,即斜线上的第几个,我们可以令 dp[i][j] 表示在阶段 i 位于从上向下第 j 个位置的最小路径和。这样定义状态是可以将此题做出来的,但是会带来很多实现上的麻烦。

我们也可以令 dp[i][j] 表示位于网格第 i 行第 j 列的最小路径和,这样阶段等于 i + j,依旧能隐式地表示阶段。

状态转移方程,由题目中每次只能向下或者向右移动一步 这句话得到,也就是 (i, j) 可以由 (i - 1, j)(i, j - 1) 移动过来,那么转移方程就是:dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

决策边界,棋盘只有一个起点,所以 dp[0][0] = grid[0][0]。如果超出棋盘,也是不行的。

记忆化搜索的代码:

class Solution {
public:
    int dp[550][550];
    vector<vector<int>> grid;

    int dfs(int x, int y) {
        // 搜不下去就是边界
        if (x == 0 && y == 0) return grid[0][0];
        if (x < 0 || y < 0) return 2100000000;

        // 记忆化
        if (dp[x][y] != -1) return dp[x][y];

        // 状态转移
        dp[x][y] = min(dfs(x - 1, y), dfs(x, y - 1)) + grid[x][y];
        return dp[x][y];
    }
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        this->grid = grid;

        memset(dp, -1, sizeof(dp));
        return dfs(n - 1, m - 1);
    }
};

如果想要使用递推,我们还需要考虑枚举状态的顺序,这里可以从上往下枚举,从左往右枚举,因为每次更新状态,需要它左边与上边状态的答案,如此枚举可以保证一个状态在被更新时,他需要的状态已经被更新完毕了。

而决策也相对更难考虑,在递推中做不到像搜索那样,搜不下去就是边界,我们需要人为地将第 0 行与第 0 列的元素都都作为决策边界。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dp[n][m] = {0};

        // 决策边界
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];

        // 状态转移
        for (int i = 1; i < n; i++){
            for (int j = 1; j < m; j++){
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[n - 1][m - 1];
    }
};

总结

  • 动态规划以状态表示为核心,需要确定转移方程与边界情况。
  • 满足三条基本性质:最优子结构、无后效性、子问题重叠。
  • 解决最值、计数、存在性判定三类问题。
  • 使用记忆化搜索或递推地方式实现。
Last modification:February 2nd, 2020 at 02:41 am
如果觉得我的文章对你有用,请随意赞赏