侧边栏
初识动态规划
发布于 | 分类于 数据结构和算法
动态规划是一种经典的算法。本文主要整理如何使用动态规划来解决一些问题。
参考
- 有了四步解题法模板，再也不害怕动态规划！
- 动态规划 - 维基百科
- 算法-动态规划 Dynamic Programming--从菜鸟到老鸟，写得很好，强烈推荐
- 拒绝遗忘：高效的动态规划算法
- 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
- 五大常用算法之二：动态规划算法，这篇文章写得比较属于术语话
- 动态规划 - letcode标签，刷起来吧
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
分治
拆分：将原问题拆分成若干个子问题； 解决：解决这些子问题； 合并：合并子问题的解得到原问题的解。
通过这三步，将大问题拆成小问题
部分算法如快排、二分查找等都是基于分治思想。
动态规划
动态规划最重要的两个概念：最优子结构和无后效性。
- 无后效性决定了是否可使用动态规划来解决。
- 最优子结构决定了具体如何解决。
无后效性指的是：子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
最优子结构指的是：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
解题思路
动态规划算法的核心就是先计算子问题，再由子问题计算父问题，记住已经解决过的子问题的解
重叠子问题、最优子结构、状态转移方程就是动态规划三要素
更常见的动态规划代码是「自底向上」进行「递推」求解：直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。
动态规划只能用于有最优子结构的问题，其含义为：局部最优解能决定全局最优解，换句话说，整个问题能够分解成子问题解决。
一般来说，一个动态规划的问题可能会解决多个重复的子问题，因此动态规划法试图仅仅解决每个子问题一次（保存已经解决子问题的答案），从而减少计算量。
动态规划往往是最能有效考察算法和设计能力的题目类型，面对这类题目最重要的是抓住问题的阶段，了解每个阶段的状态，从而分析阶段之间的关系转化。
面对动态规划的问题，我们需要先找到最优子结构（这个可能需要大量的练习），然后找到状态转移方程，通过分析子问题的答案求解较大问题的结果，进行自底向上的求解。
找到状态
可以参考这篇文章：动态规划：不同的定义产生不同的解法。
找到状态，将问题拆分成子问题，最终缩减至可以直接获取结果的基础问题，进而根据子问题求得最终结果。
“状态”可以理解为：我们需要知道什么信息，才能将原问题分解为规模更小的子问题？
一个问题，可能有多种状态的理解方式，最优的状态应该避免不必要的子问题计算
思考问题的方向
动态规划的分为了自顶向下和自底向上
自顶向下可以使用递归来解决，由于会重复计算一些底层的子问题，因此可以缓存子问题的计算结果进行优化
js
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)
}
}自底向上，我们需要先拆解问题直至底层的边界，然后利用已知答案来求解较大问题的结果，循环向前直至求得最终答案
js
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]
}一些例子
跳跃游戏
其大致思路为
js
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]不同路径
js
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);
};零钱兑换
自下向上的动态规划
js
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];
}自上向下的动态规划
js
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]
}
}在这道题可以看见动态规划中，自底向上和自顶向下两种不同的解题思路。
最长回文子串
这道题的具体思路为
- 首先从字符串中找到所有长度为1（单个字符）和为2(连续相同字符)的回文子字符串
- 对于长度为3的回文字符串而言，其中间为长度为1的回文字符串；对于长度为4的回文字符串而言，其中间为长度为2的回文子字符串；依次类推
- 因此，对于任意一个子串S[i][j]而言，只需要满足S[i+1][j-1]为回文字符串，且S[i] === S[j]，则该字符串也为回文字符串
上述过程从最小的子问题开始，依次找到较大长度的回文字符串，是一个典型的动态规划问题。
js
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
};最小路径和
整个解题思路大概如下所示
js
// 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]
// ]js
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 可以取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
依次类推，可以保存子问题的答案，然后依次求得较大问题的值，因此可以使用动态规划求解
js
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]
};解码方法
js
// 译码只能为下面两种情况
// 一位数 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]
};单词拆分
s[0~i-1][i][i+1 ~ -1]其中[i]表示在字典中的某个单词- 则问题转换为子问题：求s[0~i-1]和s[i+1 ~ -1]能够用字典表示
js
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
}
};其他
小结
动态规划最重要的就是从具体的问题中抽象状态，找到状态转移方程，然后通过代码实现状态转移的逻辑。本文大致整理了一些常见的动态规划问题，彻底理解并掌握解题方法，还需要多加练习才行。
你要请我喝一杯奶茶？
版权声明：自由转载-非商用-保持署名和原文链接。
本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。
