动态规划.md

Administrator

2021-08-11

动态规划

1106

动态规划

什么是动态规划

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

能用动态规划解决的题，有以下特点：

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

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

动态规划相关概念

状态函数：就是一个函数，一般以 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)

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

动态规划

什么是动态规划

动态规划相关概念

斐波那契 （与递归相比）

三步问题

二维网格路径数量问题

背包问题

斐波那契（与递归相比）