首页 > 程序开发 > 软件开发 > 其他 >

常用算法整理之动态规划上

2017-02-18

常用算法整理之动态规划上:动态规划是应该不能叫 一种算法,而应该叫 一类算法 或者 说是 一种思想。它和 二分查找 这种算法是不同的,二分查找我们可以用代码表示出来。

常用算法整理之动态规划上:动态规划是应该不能叫 一种算法,而应该叫 一类算法 或者 说是 一种思想。它和 二分查找 这种算法是不同的,二分查找我们可以用代码表示出来。

并且解决所有问题的思路几乎都是一样的。而动态规划其实无法用代码表示出来,每一种问题的解决方法可能用代码写出来都不一样,所以只看动态规划的定义是很难理解的,需要拿多个题目联系才能真正理解。

动态规划的特点就是把一个大的问题分解为若干个小问题,并且这些小问题之间,每一个小问题都可通过前面的小问题计算出来。通常这些小问题其实都是一个具体的状态。如果一个问题可用动态规划解决,那么需要满足如下特点:

该问题可以分解为 dp[0], dp[1], … , dp[n] 个状态,最终的答案是其中一个状态,一般是 dp[n]。(或者dp[n][m] 等更多维度,我们这里只拿一维来说) 其中 dp[i] 可以通过 dp[0] ~ dp[i-1] 或者 `dp[i+1]~dp[n] 计算出来。

如果只看定义的话,会发现DP一定是可以通过分治法的方式来解决的。那么为什么还需通过DP算法来解决呢,因为很多时候分治法算法会有大量的重复计算,而动态规划由于记录了状态,时间复杂度会有大幅下降。很多时候时间复杂度可以从 O(2^n) 降低到 O(n^2) 。如果分治法加上一个Cache来缓存已经计算过的节点,那么他的时间复杂度和DP就是一样的了,其实 DP = DC + Cache。

从上面的两个特点就可以看出来,DP 问题的难点有两个:

如果定义 dp[i],即如何拆分问题,定义状态 如何计算 dp[i],即通过之前的状态如何计算下一个状态

除了这两个难点之外,还有一点就是要处理初始值 以及可能的边界溢出问题。

另外,如果题目是要求给出所有解,肯定不用DP。DP 一般是求 最优解或者解法数。

简单的动态规划

最简单的一种动态规划,参见这一题: https://leetcode.com/problems/triangle/

这里我们用一个和题目中给出的 triangle 一样的数组 dp 来存储状态。解决上面说到的两个难点:

如果拆分问题?其实这里 dp[i][j] 就表示跳转到 triangle[i][j] 这个点所需要的最短路径。 如果计算 dp[i][j] ?dp[i][j] 其实就是取他的上层的临近节点中的比较小的一个 dp[i][j] = Math.min(last[j-1], last[j])+t[j]

然后再把边界条件处理一下,这个问题就可以解决了。代码如下:

var minimumTotal = function(triangle) {
    if(!triangle.length) return 0;
    var dp = [triangle[0]];
         //注意这里处理的初始值

    for(var i=1;i

分析一下时间复杂度,如果用 n 表示层数,那么节点数大约是 O(n^2) ,在这个算法中其实我们就对整个三角进行了一次遍历而已,所以时间复杂度也是 O(n^2)。

对比一下DC,这里我们可以很容易写一个 DC 的算法,而且比 DP 还要简单。DC算法每次计算一个节点i,j 的值的时候,都需要进行一个两个递归,分别计算 i-1,j-1 和 i-1,j,所以每次调用都会产生两个新的递归,每一层的计算量都是上一层的两倍,时间复杂度是 O(2^n)。

再看一个简单的题:https://leetcode.com/problems/unique-paths/

这里我们用 dp[i][j] 表示移动到i,j 的所有不同路径的个数。代码如下:

var uniquePaths = function(m, n) {
    var dp = [], i, j;
    for(i=0;i

中等难度的问题

上面的两个DP问题都是 Easy 难度的问题,说它 Easy 主要是对我们定义的两个难点其实都很容易解决。即很容易定义 dp[i] ,而且也很容易计算出 dp[i] 。下面的几个问题就会稍微有一些难度。

第一题,https://leetcode.com/problems/longest-increasing-subsequence/

这里我们如何定义 dp[i] 就有一些难度了,比如主要可能会有两种想法:

0~i 个元素的最长子序列 以 i 元素结尾的最长子序列

如果我们用 第一种定义,那么会发现,无法通过 dp[0] ~ dp[i-1] 来计算出 dp[i] ,因为无法知道前面的最长子序列的结尾值是否比 i 元素小。所以我们只能选择第二个定义。

即 dp[i] 表示以 i 元素结尾的最长子序列,这样我们就可以计算出 dp[i] 了,只要遍历一遍 dp[0~i-1] 找到其中小于当前元素且最长的子序列,然后长度加上自己就是 dp[i], 具体解法如下:

var lengthOfLIS = function(nums) {
    if(nums.length <= 1) return nums.length;

    var dp = [], i, result=1;

    for(i=0;i

这个做法的时间复杂度是 O(n^2) ,因为他是一个双重循环。

第二题,https://leetcode.com/problems/palindrome-partitioning-ii/

这个题目相当难,我们这里定义dp[i] 是 前i个元素所需要的最小cut。注意是 前i个 也就是不包括当前的第i个元素。至于为什么定义 前i个 而不是 0~i 个,其实主要是为了处理边界条件比较方便,定义成 0~i个 也是可以解出来的。

定义好 dp[i] 之后,我们就需要一个方法来计算出它的值。很明显的一个思路是:遍历 dp[j=0~i-1],如果 j~i 个元素是回文字符串,那么 dp[i] = dp[j]+1,只要取一个最小值就行了。

这样做的话,会出现这样的代码:

for(i=1;i<=s.length;i++) {
    for(var j=0;j

这里已经有两层循环了,也就是时间复杂度至少是 O(n^2) ,所以其中的 isPalindrome 函数我们不能再次进行循环,不然就变成 O(n^3) 了,这样肯定会超时。
有一个做法是提前计算出所有的情况,然后保存在 isPalindrome[n][n] 的数组里,这样就需要用到额外的 O(n^2) 的空间。实际在leetcode上这样做的话,会报内存超限错误的。

那么可以宣布,上述思路无法获得一个 O(n^2) 时间复杂度,并且同时空间复杂度是 O(n) 的解法。这个思路是比较容易想到的,而且实现起来不复杂。好像用Java就可以通过,但是用JS是无法通过的。贴一下这个思路的完整代码:

var minCut = function(s) {
    if(s.length <= 1) return 0;
    var isPalindrome = caculatePalindrome(s);
    var dp = [-1];

    for(var i=1;i<=s.length;i++) {
    dp.push(i-1);
    }

    for(i=1;i<=s.length;i++) {
        for(var j=0;j

这里我们换一个思路,这个思路非常难想。就是我们其实在第二层循环的同时,就能判断出是否是回文字符串了,不需要额外的一次判断。具体的方式,我们直接看代码来说明:

var minCut = function(s) {
    if(s.length <= 1) return 0;
    var dp = [];

    for(var i=0;i<=s.length;i++) {
        dp.push(i-1);
    }

    for(i=0;i<=s.length;i++) {
        for(var j=0;i-j>=0 && i+j=0 && i+j

这个解法是参考最高票的那个答案的。在第二层循环的时候,如果是计算dp[i+1] ,那么肯定无法直接判断是不是回文字符串,所以这个方法做了一个很巧妙的设计:计算 dp[i+j+1] 而不是计算 dp[i+1]。这样在j逐步递增的时候我们就可以判断出 i-j ~ i+j 是不是一个回文字符串了。

很容易看出来这个解法的时间复杂度是 O(n^2)

第三题,https://leetcode.com/problems/word-break/

这个题相对简单一些,还是和前一题的思路类似,用 dp[i] 表示 前i个元素是不是能切割成单词,然后这里比上一题简单的地方就是,上一题的回文字符串不好判断,这里是不是在词典中就很容易判断出来了,具体解法如下:

var wordBreak = function(s, wordDict) {
    var maxWordLength = 0;
    wordDict.forEach(function(w){
        maxWordLength = Math.max(w.length, maxWordLength);
    });

    var dp = [true];

    for(var i=1;i<=s.length;i++) dp.push(false);

    for(i=1;i<=s.length;i++) {
        for(var j=1;j<=maxWordLength && j<=i;j++) {
            if(wordDict.has(s.slice(i-j,i)) && dp[i-j]) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length];
};

注意一个地方,就是第二层循环的时候,j的最大值不是i 而是 maxWordLength,所以时间复杂度是 O(NL) 而不是 O(n^2),其中L就是 maxWordLength。

先介绍上面这几种相对简单的动态规划题,除了 回文字符串比较难,其他的都是 Easy 或者 Medium 级别的,属于需要做到 bug free 的题目。

下次继续讲更复杂的动态规划题,这些题目的特点就是考两个序列间的一些操作。

相关文章
最新文章
热点推荐