侧边栏

初识动态规划

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

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

参考

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

分治

拆分:将原问题拆分成若干个子问题; 解决:解决这些子问题; 合并:合并子问题的解得到原问题的解。

通过这三步,将大问题拆成小问题

部分算法如快排、二分查找等都是基于分治思想。

动态规划

动态规划最重要的两个概念:最优子结构和无后效性。

  • 无后效性决定了是否可使用动态规划来解决。
  • 最优子结构决定了具体如何解决。

无后效性指的是:子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。

最优子结构指的是:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。

解题思路

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

重叠子问题、最优子结构、状态转移方程就是动态规划三要素

更常见的动态规划代码是「自底向上」进行「递推」求解:直接从最底下、最简单、问题规模最小、已知结果的 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]
}

一些例子

跳跃游戏

letcode传送门

其大致思路为

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]

不同路径

letcode传送门:62不同路径

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);
};

零钱兑换

letcode传送门:322. 零钱兑换

自下向上的动态规划

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]
    }
}

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

最长回文子串

letcode传送门

这道题的具体思路为

  • 首先从字符串中找到所有长度为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
};

最小路径和

letcode传送门

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

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]
};

除数博弈

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

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

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]
};

解码方法

letcode传送门

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]
};

单词拆分

letcode传送门

  • 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
    }
};

其他

小结

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

你要请我喝一杯奶茶?

版权声明:自由转载-非商用-保持署名和原文链接。

本站文章均为本人原创,参考文章我都会在文中进行声明,也请您转载时附上署名。