动态规划.md

何言 2021年08月11日 96次浏览

动态规划

什么是动态规划

动态规划,Dynamic Programming,简称 DP。这个词其实是运筹学的一个分支,在求解决策中占重要地位。当然这里只是取其一个狭义的意思,就是算法题中的一种解题的方法,或者说思考方法。

能用动态规划解决的题,有以下特点:

  1. 问题能进行拆分,大问题能拆分成小问题,并且这些问题都有共同的特点
  2. 这些问题能转换成一个函数,有输入和输出。
  3. 这个函数的递推表达式容易得出

有点抽象,不理解也可以直接往后看,相信看完之后你就能理解了(这里要重点区分一下递归,递归的也是问题的拆分,不过和动态规划还是有点区别的)

动态规划相关概念

  • 状态函数:就是一个函数,一般以 dp 命名。可以是一元,也可以是多元的。

  • 状态转移方程:就是状态函数的递推公式,例如 : dp(i) = dp(i-1)*2 + dp(i-2)

  • 边界条件:状态转移方程中转移的起点,即在状态转移方程中不合法的输入,例如:

    对于 dp(i) = dp(i-1)*2 + dp(i-2) 假设 状态函数 的定义域为 i > 0,则边界条件为

    dp(1)dp(2) ,因为这两个值如果用状态转移方程表示则会出现 dp(-1) 这种非法的条件,因此这两个函数值要手动给出。

斐波那契 (与递归相比)

  • 题目:实现斐波那契函数 int fibonacci(i)

斐波那契简单,很容易写出这个函数的解析式:

f(0) = 0
f(1) = 1
f(i) = f(i-1) + f(i-2), i > 1

假如你用递归写:

int fibonacci(int i){
    if(i == 0) return 0;
    else if(i == 1) return 1;
    else return fibonacci(i-1) + fibonacci(i-2);
}

还是很好理解的,我们来分析一下复杂度:

  • 时间复杂度:可以看成高度为 n 的二叉树的节点数(2^n -1),也就是 O(2^n)
  • 空间复杂度:递归树的高度,也就是 O(n)

指数型的复杂度,其效率是非常低的,但如果我们采用动态规划的写法:

int fibonacci(int i){
    vector<int> dp(i+1);
    dp[0] = 0;
    dp[1] = 1;
    for(int j = 2 ; j <= i ; ++ j){
        dp[j] = dp[j-1]+dp[j-2];
    }
    return dp[i];
}

可以看到复杂度:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

可以看到,动态规划的做法是 线性时间复杂度,其实动态规划的本质就是一种类似 记忆化递归 的东西,当一个数据计算过一次之后,第二次就直接获取,而不用像 纯递归 一样再开一棵子树去计算。

而在本题中,我们使用了一个 dp 的数组作为 状态函数,先设定边界条件 dp(0) 与 dp(1) ,然后通过迭代不断往上计算到 dp(i) 。这是最简单的一种动态规划题,实际上的动态规划会很灵活。

接下来介绍一下几道动态规划的经典题目:三步问题、二维网格路径数量问题和背包问题

三步问题

  • 题目:有个小孩正在上楼梯,楼梯有 n 阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。

  • 确定状态函数:dp(n) 表示 n 阶台阶小孩上楼梯的方式数量

  • 确定状态转移方程:dp(n) = dp(n-1) + dp(n-2) + dp(n-3)

    这里简单说明一下:假设 n = 4,则所有上楼梯的方法中,我们按照小孩最后一步上多少级台阶分成三种情况,假设小孩最后上 1 级台阶,则方法等价于 3 阶台阶的所有方法最后再加上一阶即可。同理二级三级也一样,因此 dp(4) = dp(3) + dp(2) + dp(1),最终归纳出一般方程。

  • 确定边界条件:因为状态转移方程中有 dp(n-1) dp(n-2) dp(n-3),因此边界条件为 :dp(1) dp(2) 和 dp(3),并且其值可以简单穷举,得到 dp(1) = 1,dp(2) = 2,dp(3) = 4

然后可以得出代码:

int waysToStep(int n) {
    vector<int> dp(n+1+1);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int j = 4 ; j <= n ; ++ j){
        dp[j] = dp[j-1]+dp[j-2]+dp[j-3];
    }
    return dp[n];
}

二维网格路径数量问题

  • 问题 :一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

    问总共有多少条不同的路径?

这个问题也是一个典型的动态规划问题,不过是二维的。

  • 建立状态函数: dp(i, j) 表示机器人从左上角到 i 格宽 j 格高的 网格的右下角的路径数量
  • 建立状态转移:这里以最后一步分类,若左后一步往下走,则路径数量为 dp(i, j-1),若最后一步往右走,则路径数量为 dp(i-1, j),因此状态转移方程为: dp(i,j) = dp(i, j-1) + dp(i-1, j)
  • 边界条件:dp(1, j) = dp(i, 1) = 1

直接上代码:

int uniquePaths(int m, int n) {
    vector<vector<int>> f(m+1,vector<int>(n+1, 1));
    for(int i =2; i < m ; ++i){
        for(int j=2 ; j < n ; ++j){
            f[i][j]=f[i-1][j]+f[i][j-1];
        }
    }
    return f[m][n];
}

时间复杂度:O(mn)

空间复杂度:O(mn)

背包问题

背包问题有很多分支:01背包、完全背包、多重背包等,之后可能会单独开一章,这里只讲一下 最简单的 01 背包。

  • 一共有 n 个物品,给你两个数组 v 和 w,其中 v[i] 代表 第 i 件物品的价值,w[i] 代表第 i 件物品的重量。给你一个容量 c 代表背包能装上的最大重量和。请你设计一个算法,求出背包能装入物品的最大价值和。

首先,对于 n 个物品,分别有装入和不装入两种状态,如果使用暴力穷举,我们需要 O(2^n) 的复杂度去遍历,这实在是无法接受。考虑使用动态规划。

  • 建立状态函数:dp(n, m) 表示 前 n 件物品装入重量上限为 m 的背包的最大价值。

  • 建立状态转移:对于 dp(n, m),分两种情况,第 n 个物品装入或者不装入

    • 若装入,则 此时最大价值为 dp(n-1, m-w[n]) + v[n],当然要求要能装入,则 m-w[n] > 0
    • 若不装入,则 此时最大价值为 dp(n-1, m)
    • 因此两种情况综合,总的转移方程为: dp(n, m) = max{ dp(n-1, c-w[n]) + v[n], dp(n-1, m)}

    这里还是举个例子,假设我要求 dp(3, 10),即前三件物品装入容量为 10 的背包的最大价值,我们分为两种情况,一是 第三件物品不装,则此时最大价值为 dp(2, 10),则把前两件物品装入容量为 10 的背包的最大价值(因为第三件不装,因此等价与前两件)。二是 第三件物品装入,则此时最大价值为 dp(2, 10 - w[n]) + v[n],因为第三件装入了,则前两件可装入的容量要减去第三件物品的重量。求出此时前两件物品的最大价值再加上第三件的价值即可。最终整体就是两种情况的最大值。

  • 边界条件:这里边界条件为 dp(0, m),因为没有物品,因此全部为 0 。

来看代码:

int knapsack(vector<int> w, vector<int> v, int c, int n){
    vector<vector<int>> dp(n+1, vector<int>(c+1));
    for(int i = 1 ; i < n+1 ; ++ i){
        for(int j = 0 ; j < c+1 ; ++ j){
            int put = 0; // 第 n 件装入的价值
            int noPut = 0; // 第 n 件不装入的价值
            if(j >= w[i]){ // 第 n 件能装入
                put = dp[i-1][j-w[i]] + v[i];
            }
            noPut = dp[i-1][j];
            dp[i][j] = max(put, noPut);
        }
    }
    return dp[n][c];
}
  • 时间复杂度: O(n*c)
  • 空间复杂度: O(n*c)

当然,背包问题是可以优化的,在之后的背包专题中在考虑把,这里只需要建立动态规划的思维即可。