ShymeanV0.8.0

初识动态规划

发表于| 分类于数据结构和算法

动态规划是一种经典的算法。本文主要整理如何使用动态规划来解决一些问题。

<!--more-->

参考

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

1. 动态规划

1.1. 解题思路

动态规划算法的核心就是先计算子问题，再由子问题计算父问题，记住已经解决过的子问题的解

动态规划只能用于有最优子结构的问题，其含义为：局部最优解能决定全局最优解，换句话说，整个问题能够分解成子问题解决。

一般来说，一个动态规划的问题可能会解决多个重复的子问题，因此动态规划法试图仅仅解决每个子问题一次（保存已经解决子问题的答案），从而减少计算量。

动态规划往往是最能有效考察算法和设计能力的题目类型，面对这类题目最重要的是抓住问题的阶段，了解每个阶段的状态，从而分析阶段之间的关系转化。

面对动态规划的问题，我们需要先找到最优子结构（这个可能需要大量的练习），然后找到状态转移方程，通过分析子问题的答案求解较大问题的结果，进行自底向上的求解。

1.2. 找到状态

可以参考这篇文章：动态规划：不同的定义产生不同的解法。

找到状态，将问题拆分成子问题，最终缩减至可以直接获取结果的基础问题，进而根据子问题求得最终结果。

“状态”可以理解为：我们需要知道什么信息，才能将原问题分解为规模更小的子问题？

一个问题，可能有多种状态的理解方式，最优的状态应该避免不必要的子问题计算

1.3. 思考问题的方向

动态规划的分为了自顶向下和自底向上

自顶向下可以使用递归来解决，由于会重复计算一些底层的子问题，因此可以缓存子问题的计算结果进行优化

function fibonacci(n) {
    var memo = []
    return step(n)
    function step(n) {
        if (n <= 1) { return n }
        if (memo[n]) {
            return memo[n]
        }
        // 为了求n，则需要知道n-1和n-2的值，因此使用递归依次计算，最后将他们相加得到最终结果
        return step(n - 1) + step(n - 2)
    }
}

自底向上，我们需要先拆解问题直至底层的边界，然后利用已知答案来求解较大问题的结果，循环向前直至求得最终答案

function fibonacci(n) {
    var ans = []
    ans[0] = 1
    ans[1] = 1

    for (var i = 2; i <= n; ++i) {
        // 利用已知的0和1的答案，依次求得较大值2、3...n的答案
        ans[i] == ans[i - 1] + ans[i - 2]
    }
    return ans[n]
}

2. 一些例子

2.1. 跳跃游戏

letcode传送门

其大致思路为

var canJump = function (nums) {
  var memo = {} // 记录某个位置是否可以到末尾点
  var len = nums.length
  memo[len-1] = true
  for(var i = len - 2; i >= 0; --i){
    var cur = nums[i]
    memo[i] = false
    for(var j = 1; j <= cur; ++j){
      // 只要当前元素能到达的位置中有一个能到达末尾，则当前元素可到达末尾
      if(memo[j+i]){
        memo[i] = true
        break
      }
    }
  }
  return memo[0]

2.2. 不同路径

letcode传送门：62不同路径

var uniquePaths = function(m, n) {
    let map = new Map();
    function step(m, n) {
        if (m == 1) { return 1; }
        if (n == 1) { return 1; }
        let key = m + "," + n;
        if (map.has(key)) { return map.get(key); }

        let res = step(m - 1, n) + step(m, n - 1);

        map.set(key, res);

        return res;
    }

    return step(m, n);
};

2.3. 零钱兑换

letcode传送门:322. 零钱兑换

自下向上的动态规划

var coinChange = function (coins, amount) {
    var dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0

    // F[i] = min(F(i - c1), F(i - c2)...) + 1， 其中c1..cn为每个硬币的面值
    // 在计算 F(i) 之前，我们可以先计算出 F(0) ~ F(i-1) 的答案
    for (var i = 1; i <= amount; ++i) {
        for (var j = 0; j < coins.length; ++j) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

自上向下的动态规划


var coinChange = function (coins, amount) {
    if (amount < 0) {
        return 0
    }
    var dp = {}

    var res = step(amount)
    return res

    // F(S) ，对于金额 S 最少的硬币数，所得组合的最后一枚硬币的面值是 C，则F(S) = F(S - C) + 1
    // 由于不知道所得组合中最后一枚硬币的面值，因此遍历coins，依次找到满足题意的组合，并取出最小值
    function step(amount) {
        // 无法在coins找到
        if (amount < 0) {
            return -1
        }
        // 刚好完成组合
        if (amount === 0) {
            return 0
        }
        // 自顶向下时会存在大量重复的计算，可以缓存已经访问过的记录
        if (dp[amount]) {
            return dp[amount]
        }

        let min = Infinity
        for (var j = 0; j < coins.length; ++j) {
            // 找到满足题意的最后一枚硬币的组合
            var res = step(amount - coins[j])
            if (res >= 0 && res < min) {
                min = 1 + res
            }
        }

        dp[amount] = min === Infinity ? -1 : min
        return dp[amount]
    }
}

在这道题可以看见动态规划中，自底向上和自顶向下两种不同的解题思路。

2.4. 最长回文子串

letcode传送门

这道题的具体思路为

  • 首先从字符串中找到所有长度为1（单个字符）和为2(连续相同字符)的回文子字符串
  • 对于长度为3的回文字符串而言，其中间为长度为1的回文字符串；对于长度为4的回文字符串而言，其中间为长度为2的回文子字符串；依次类推
  • 因此，对于任意一个子串S[i][j]而言，只需要满足S[i+1][j-1]为回文字符串，且S[i] === S[j]，则该字符串也为回文字符串

上述过程从最小的子问题开始，依次找到较大长度的回文字符串，是一个典型的动态规划问题。

var longestPalindrome = function (s) {
    var memo = {}
    var len = s.length
    // 找到所有长度为1和2的回文字符串
    for (var i = 0; i < len; ++i) {
        memo[s[i]] = true
        if (s[i + 1] && s[i] === s[i + 1]) {
            var sub = s[i] + s[i + 1]
            memo[sub] = true
        }
    }

    // 找到所有长度大于2的回文字符串
    for (var c = 3; c <= len; ++c) {
        for (var i = 0; c - 1 + i < len; ++i) {
            var mid = s.substr(i + 1, c - 2) // 如果mid为回文，则sub只需要满足首尾字符相同，则也为回文字符串
            var start = s[i]
            var last = s[c + i - 1]
            if (start === last && memo[mid]) {
                var sub = start + mid + last
                memo[sub] = true
            }
        }
    }
    var ans = ''
    Object.keys(memo).forEach(item => {
        if (ans.length < item.length) {
            ans = item
        }
    })

    return ans
};

2.5. 最小路径和

letcode传送门

整个解题思路大概如下所示

// 2*2
// [
//     [1, 2], // [1, 1+2]
//     [3, 4] // [1+3, 4 + min(1+2, 1+3)] // 取左侧和上方较小值
// ]
// 2*3
// [
//     [1, 2, 5], // [1, 1+2 = 3, 1+2+5 = 8]
//     [3, 4, 6] // [1+3 = 4, 4 + min(3, 4) = 7, 6 + min(7, 8) = 13]
// ]
var minPathSum = function (grid) {
    var r = grid.length
    if (r == 0) {
        return 0
    }
    var c = grid[0].length
    for (var i = 0; i < r; ++i) {
        for (var j = 0; j < c; ++j) {
            var min
            if (i == 0 && j == 0) {
                min = 0
            } else if (j == 0 && i >= 1) {
                min = grid[i - 1][j]
            } else if (i == 0 && j >= 1) {
                min = grid[i][j - 1]
            } else {
                // 计算左侧或上方较小值
                min = Math.min(grid[i - 1][j], grid[i][j - 1])
            }
            grid[i][j] += min
        }
    }
    return grid[r - 1][c - 1]
};

2.6. 除数博弈

letcode传送门

本题思路为

  • 2 可以取1，对方为1，false
  • 3 可以取1，对方为2，false
  • 4 可以取1、2，最后取1,然后对方为3,true
  • 5 可以取1,然后对方为4,false
  • 6 可以取1、2、3，取3,然后对方为3,true
  • 7，可以取1，对方为6，false

依次类推，可以保存子问题的答案，然后依次求得较大问题的值，因此可以使用动态规划求解

var divisorGame = function (N) {
    var memo = {}
    memo[1] = false

    for (var n = 1; n <= N; ++n) {
        for (var x = 1; x < n; ++x) {
            if (n % x === 0) {
                if (!memo[n - x]) {
                    memo[n] = true
                    break
                }
            }
            memo[n] = false
        }
    }
    return memo[N]
};

2.7. 解码方法

letcode传送门

// 译码只能为下面两种情况
// 一位数 1-9
// 二位数 1 + 1-9 和 2 + 1-6

// 动态规划通用推算公式
// dp[i]表示 str[0...i]的译码方法总数
// 如果s[i] === '0'， 如果s[i-1]为'1'或'2'，则dp[i] === dp[i-2]，否则return 0
// 如果s[i-1] === '1'，则dp[i] = dp[i-1](解释：s[i-1]与s[i]分开译码) + dp[i-2](解释：最后两位合并译码)
// 如果s[i-1] === '2'，且'1'<=s[i]<='6'，则dp[i] = dp[i-1] + dp[i-2]

var numDecodings = function (s) {
    if (s[0] === '0') {
        return 0
    }

    // 由于只使用了memo[i-1]和memo[i-1]，因此还可以使用两个变量将空间复杂度将为O(1)
    var memo = {
        '-1': 1,
        '0': 1
    }

    for (var i = 0; i <= s.length; ++i) {
        var cur = s[i]
        var prev = s[i - 1]
        if (cur === '0') {
            if (prev === '1' || prev === '2') {
                memo[i + 1] = memo[i - 1]
            } else {
                return 0
            }
        } else if ((prev === '2' && cur <= '6') || (prev === '1' && cur <= '9')) {
            memo[i + 1] = memo[i] + memo[i - 1]
        } else {
            memo[i + 1] = memo[i]
        }
    }
    return memo[s.length]
};

2.8. 单词拆分

letcode传送门

  • s[0~i-1][i][i+1 ~ -1]其中[i]表示在字典中的某个单词
  • 则问题转换为子问题：求s[0~i-1]和s[i+1 ~ -1]能够用字典表示
var wordBreak = function (s, wordDict) {
    var memo = {}
    return step(s, wordDict)

    function step(s, wordDict) {
        if (typeof memo[s] !== 'undefined') {
            return memo[s]
        }

        if (!s) {
            return true
        }
        for (var i = 0; i < wordDict.length; ++i) {
            var word = wordDict[i]
            var idx = s.indexOf(word)
            if (idx === -1) {
                continue
            }
            var s1 = s.slice(0, idx)
            var s2 = s.slice(idx + word.length)
            var flag = true

            if (s1) {
                memo[s1] = step(s1, wordDict)
                flag = flag && memo[s1]
            }
            if (s2) {
                memo[s2] = step(s2, wordDict)
                flag = flag && memo[s2]
            }
            if (flag) {
                return true
            }
        }
        return false
    }
};

2.9. 其他

3. 小结

动态规划最重要的就是从具体的问题中抽象状态，找到状态转移方程，然后通过代码实现状态转移的逻辑。本文大致整理了一些常见的动态规划问题，彻底理解并掌握解题方法，还需要多加练习才行。

世人的悲欢并不相通，我只是觉得他们吵闹。

Copyright © Shymean 2016 - 2024蜀ICP备2023029820号