开启成长之旅!这是我参加「日新计划 12 月更文挑战」的第24天,点击查看活动详情。

学习目标:完全搞懂最优子结构、无后效性和重复子问题。什么样的问题能够用动态规划处理?处理动态规划问题的一般考虑过程是什么样的?贪心、分治、回溯、动态规划这四种算法思维又有什么区别和联系?

一,“一个模型三个特征”理论解说

一个模型指的是合适用动态规划算法处理的问题的模型,这个模型也被界说为“多阶段决议计划最优解模型”。具体解释如下:

一般是用动态规划来处理最优问题。而处理问题的过程,需求阅历多个决议计划阶段。每个决议计划阶段都对应着一组状况。然后咱们寻觅一组决议计划序列,经过这组决议计划序列,能够发生终究希望求解的最优值。

1. 最优子结构

最优子结构指的是,问题的最优解包括子问题的最优解。反过来说便是,咱们能够经过子问题的最优解,推导出问题的最优解。把最优子结构,对应到前面界说的动态规划问题模型上,便是后边阶段的状况能够经过前面阶段的状况推导出来

2. 无后效性

无后效性有两层意义,榜首层意义是,在推导后边阶段的状况的时分,咱们只关怀前面阶段的状况值,不关怀这个状况是怎么一步一步推导出来的。第二层意义是,某阶段状况一旦确认,就不受之后阶段的决议计划影响。无后效性是一个十分“宽松”的要求。只需满意前面说到的动态规划问题模型,其实基本上都会满意无后效性。

3. 重复子问题

不同的决议计划序列,到达某个相同的阶段时,可能会发生重复的状况。

4. “一个模型三个特征”实例剖析

结合一个具体的动态规划问题更能具体理解上述理论,示例问题描述如下

假定咱们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始方位在左上角,停止方位在右下角。咱们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角,会有许多不同的途径能够走。咱们把每条途径经过的数字加起来看作途径的长度。那从左上角移动到右下角的最短途径长度是多少呢?

深入浅出动态规划算法(中)

min_dist(i, j) 能够经过 min_dist(i, j-1)min_dist(i-1, j) 两个状况推导出来,所以这个问题契合“最优子结构”。

min_dist(i, j) = min(min_dist(i-1,j), min_dist(i, j-1))

二,两种动态规划解题思路总结

知道了怎么鉴别一个问题是否能够用动态规划来处理,接下来便是总结动态规划处理问题的一般思路。处理动态规划问题,一般有两种思路。别离叫作:状况搬运表法和状况搬运方程法。

1. 状况搬运表法

一般能用动态规划处理的问题,都能够运用回溯算法的暴力搜索处理。所以,当咱们拿到问题的时分,咱们能够先用简单的回溯算法处理,然后界说状况,每个状况表示一个节点,然后对应画出递归树。从递归树中,咱们很简单能够看出来,是否存在重复子问题,以及重复子问题是怎么发生的。以此来寻觅规律,看是否能用动态规划处理。

找到重复子问题之后,接下来,咱们有两种处理思路,榜首种是直接用回溯加“备忘录”的办法,来防止重复子问题。从执行功率上来讲,这跟动态规划的处理思路没有不同。第二种是运用动态规划的处理办法,状况搬运表法

咱们先画出一个状况表。状况表一般都是二维的,所以你能够把它幻想成二维数组。其间,每个状况包括三个变量,行、列、数组值。咱们依据决议计划的先后过程,从前往后,依据递推联系,分阶段填充状况表中的每个状况。最后,咱们将这个递推填表的过程,翻译成代码,便是动态规划代码了。

合适状况是二维的情况,再多维的话就不合适了,究竟人脑不合适处理高维度的问题。

起点到结尾,有许多种不同的走法,回溯算法比较合适无重复又不遗漏地穷举出一切走法,然后对比找出一个最短走法。

1,回溯解法的 C++ 代码如下:

// leetcode64. 最小途径和. 回溯法-会超出时间约束
class Solution {
private:
    int minDist = 10000;
    void minDistBT(vector<vector<int>>& grid, int i, int j, int dist, int m, int n) {
        if (i == 0 && j == 0) dist = grid[0][0];
        if (i == m-1 && j == n-1) {
            if (dist < minDist) minDist = dist;
            return;
        }
        if (i < m-1) {
            minDistBT(grid, i + 1, j, dist + grid[i+1][j], m, n);  // 向右走
        }
        if (j < n-1) {
            minDistBT(grid, i, j + 1, dist + grid[i][j+1], m, n);  // 向下走
        }
    }
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int dist = 0;
        minDistBT(grid, 0, 0, dist, m, n);
        return minDist;
    }
};

有了回溯代码之后,接下来,自然要画出递归树,以此来寻觅重复子问题。在递归树中,一个状况(也便是一个节点)包括三个变量 (i, j, dist),其间 ij 别离表示行和列,dist 表示从起点到达 (i, j) 的途径长度。从图中,能够看出,虽然 (i, j, dist) 不存在重复,可是 (i, j) 重复的有许多。对于 (i, j) 重复的节点,咱们只需求挑选 dist 最小的节点,继续递归求解,其他节点就能够放弃了。

深入浅出动态规划算法(中)

2,动态规划解法的 C++ 代码如下:

// 对应 leetcode64. 最小途径和
class Solution {  // 动态规划:状况搬运表法
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > states(m, vector<int>(n, 0));
        // 榜首个阶段初始化
        int sum = 0;
        for(int i=0; i<n;i++){  // 初始化 states 的榜首行数据
            sum += grid[0][i];
            states[0][i] = sum;
        }
        sum = 0;
        for(int j=0; j<m; j++){  // 初始化 states 的榜首列数据
            sum += grid[j][0];
            states[j][0] = sum;
        }
        // 分阶段求解,下层状况的值是基于上一层状况来的
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                states[i][j] = grid[i][j] + std::min(states[i-1][j],states[i][j-1]);
            }
        }
        return states[m-1][n-1];
    }
};

深入浅出动态规划算法(中)

2. 状况搬运方程法

依据最优子结构,写出递归公式,也便是所谓的状况搬运方程。状况搬运方程,或者说递归公式是处理动态规划的要害。递归加“备忘录”的方法,将状况搬运方程翻译成来 C++ 代码。

// 状况搬运方程
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
// 对应 leetcode64. 最小途径和
class Solution {  // 状况搬运方程法
private:
    int minDist(int i, int j, vector<vector<int> >& matrix, vector<vector<int> >& mem) { // 调用minDist(n-1, n-1);
        if (i == 0 && j == 0) return matrix[0][0];
        if (mem[i][j] > 0) return mem[i][j];
        int minUp = 10000;
        if (i - 1 >= 0) minUp = minDist(i - 1, j, matrix, mem);
        int minLeft = 10000;
        if (j - 1 >= 0) minLeft = minDist(i, j - 1, matrix, mem);
        int currMinDist = matrix[i][j] + std::min(minUp, minLeft);
        mem[i][j] = currMinDist;
        return currMinDist;
    }
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > mem(m, vector<int>(n, -1));
        return minDist(m - 1, n - 1, grid, mem);
    }
};

深入浅出动态规划算法(中)

三,四种算法比较剖析

如果将这四种算法思维分一下类,那贪心、回溯、动态规划能够归为一类,而分治独自能够作为一类,由于它跟其他三个都不大一样。为什么这么说呢?由于前三个算法处理问题的模型,都能够笼统成多阶段决议计划最优解模型,而分治算法处理的问题虽然大部分也是最优解问题,可是,大部分都不能笼统成多阶段决议计划模型。

虽然动态规划比回溯算法高效,可是,并不是一切问题,都能够用动态规划来处理。能用动态规划处理的问题,需求满意三个特征,最优子结构、无后效性和重复子问题。在重复子问题这一点上,动态规划和分治算法的区别十分明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相反,动态规划之所以高效,便是由于回溯算法完结中存在很多的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它处理问题起来愈加高效,代码完结也愈加简练。不过,它能够处理的问题也愈加有限。它能处理的问题需求满意三个条件,最优子结构、无后效性和贪心挑选性(这儿咱们不怎么强调重复子问题)。其间,最优子结构、无后效性跟动态规划中的无异。“贪心挑选性”的意思是,经过部分最优的挑选,能发生大局的最优挑选。每一个阶段,咱们都挑选当前看起来最优的决议计划,一切阶段的决议计划完结之后,终究由这些部分最优解构成大局最优解。

四,内容总结

什么样的问题合适用动态规划处理?这些问题能够总结归纳为“一个模型三个特征”。其间,“一个模型”指的是,问题能够笼统成分阶段决议计划最优解模型。“三个特征”指的是最优子结构、无后效性和重复子问题。

哪两种动态规划的解题思路?它们别离是状况搬运表法和状况搬运方程法。其间,状况搬运表法解题思路大致能够归纳为,回溯算法完结 – 界说状况 – 画递归树 – 找重复子问题 – 画状况搬运表 – 依据递推联系填表 – 将填表过程翻译成代码。状况搬运方程法的大致思路能够归纳为,找最优子结构 – 写状况搬运方程 – 将状况搬运方程翻译成代码

练习题

假定咱们有几种不同币值的硬币 v1,v2,……,vn(单位是元)。如果咱们要支付 w 元,求最少需求多少个硬币。比方,咱们有 3 种不同的硬币,1 元、3 元、5 元,咱们要支付 9 元,最少需求 3 个硬币(3 个 3 元的硬币)。

参考资料

动态规划理论:一篇文章带你完全搞懂最优子结构、无后效性和重复子问题