算法【动态规划篇】

[SampsonKY]

动态规划的思想

• 首先，动态规划问题的一般形式是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如求最长递增子序列，最小编辑距离等等。

• 求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。

• 但这类穷举有点特别，因为这类问题存在重叠子问题，如果暴力穷举的话效率会极其低下，所以需要**「备忘录」或者「DP table」**来优化穷举过程，避免不必要的计算。

• 动态规划问题一定会具备「最优子结构」，并且子问题见必须相互独立，才能通过子问题的最值得到原问题的最值。

• 穷举所有可行解其实并不是一件容易的事，只有列出**正确的「状态转移方程」**才能正确地穷举。

• 求解此类问题思想框架：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

//初始化 base case
dp[0][0][...] = base
//进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

斐波那契数列

这个例子不是纯粹的动态规划，只是很好的引出了动态规划的问题。

暴力递归

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

毫无疑问，这种写法虽然简洁易懂，但效率不高。

递归算法时间复杂度计算方式：用子问题个数乘以解决一个子问题所需要的时间

在此例中，子问题个数为 O(2^n^)，解决子问题的时间为 O(1)。时间复杂度为两者乘积 O(2^n^)，指数级别，爆炸！！！

通过分析可以明显发现算法效率低的原因：存在大量重复计算。

这就是动态规划问题的第一个性质：重叠子问题。

带备忘录的递归解法

思想：建立一个【备忘录】，每次算出子问题答案后先记到【备忘录】中再返回，每次遇到一个子问题先去【备忘录】里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个备忘录，当然也可以使用哈希表（字典）。

int fib(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    vector<int> memo(N + 1, 0);
    // 进行带备忘录的递归
    return helper(memo, N);
}

int helper(vector<int>& memo, int n) {
    // base case 
    if (n == 1 || n == 2) return 1;
    // 已经计算过
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

改进后的算法，子问题个数为 O(n)，时间复杂度为O(n)

至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

动态规划一般都脱离了递归，而是由循环迭代完成计算。

dp 数组的迭代解法

把这个「备忘录」独立出来成为一张表，就叫做 DP table ，在这张表上完成「自底向上」的推算。

int fib(int N) {
    vector<int> dp(N + 1, 0);
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

这里，引出**「状态转移方程」**这个名词，实际上就是描述问题结构的数学形式：

其实上面几种解法，都是围绕这个方程式展开的不同表现形式。列出「状态转移方程」的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法。

优化

int fib(int n) {
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)

这个技巧就是所谓的「状态压缩」。

凑零钱问题

题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

分析：这个问题是动态规划问题，因为它具有【最优子结构】，并且子问题相互独立。比如相求amount=11时（原问题），如果知道凑出amount=10的最少硬币数（子问题），只需要把子问题的答案加一就是原问题的解。因为硬币数量没有限制，所以子问题间没有相互制约，是相互独立的。

如何列出正确的状态转移方程

1. 确定 base case
2. 明确dp函数/数组的定义
3. 找出dp函数/数组与子问题的关系

int coinChange(vector<int>& coins, int amount) {
    // 数组大小为 amount + 1，初始值也为 amount + 1
    vector<int> dp(amount + 1, amount + 1);
    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.size(); i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

典型例题

构造回文的最小插入次数

题目

输入一个字符串 s，你可以在字符串的任意位置插入任意字符。如果要把 s 变成回文串，请你计算最少要进行多少次插入？

函数签名如下：

int minInsertions(string s);

比如说输入 s = "abcea"，算法返回 2，因为可以给 s 插入 2 个字符变成回文串 "abeceba" 或者 "aebcbea"。如果输入 s = "aba"，则算法返回 0，因为 s 已经是回文串，不用插入任何字符。

思路

• 定义一个二维的 dp 数组，dp[i][j]的定义如下：对字符串 s[i..j]，最少需要进行 dp[i][j] 次插入才能变成回文串。

• base case：当 i===j时，dp[i][j] = 0，因为当 i == j 时 s[i..j] 就是一个字符，本身就是回文串，所以不需要进行任何插入操作。

• 假设已经计算出子问题 dp[i+1][j-1]的值，即已确认s[i+1…j-1]是一个回文，求dp[i][j]

  • 如果s[i] === s[j]，不需要进行插入，此时 dp[i][j]=dp[i+1][j-1]
  • 如果 s[i] !== s[j]
    • 先将s[i..j-1]或s[i+1...j]变成回文串，选择其中代价小的。
    • 根据前一步的选择，将 s[i...j] 变成回文。
    • 即：dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1

• 因为状态转移方程中 dp[i][j] 和 dp[i+1][j]，dp[i][j-1]，dp[i+1][j-1] 三个状态有关，为了保证每次计算 dp[i][j] 时，这三个状态都已经被计算，我们一般选择从下向上，从左到右遍历 dp 数组：

  

代码

function minInsertions(s){
    let n = s.length
    // 定义：对 s[i..j]，最少需要插入 dp[i][j] 次才能变成回文
    let dp=new Array(n)
    // base case：i == j 时 dp[i][j] = 0，单个字符本身就是回文
    // dp 数组已经全部初始化为 0，base case 已初始化
    for(let i=0;i<n;i++){
        dp[i]=new Array(n).fill(0) 
    }
    for(let i = n-2; i>=0; i--){
        for(let j= i+1; j<n; j++){
            if(s[i] == s[j]){
                dp[i][j] = dp[i+1][j-1]
            } else {
                dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1])+1
            }
        }
    }
    return dp[0][n-1]
}

leetcode 题目

矩阵路径

• No.64 最小路径和
• No.62 不同路径

重要参考

labuladong的算法小抄

CS-Notes