动态规划学习的一点心得

发布日期：2020-04-18 17:57:56

DP动态规划算法

动态规划来解决一些最优解的问题，常常可以将暴力算法的指数级时间复杂度降到O(n2)和O(n3)。动态规划并不难，只要按四个步骤就能找出最优解。

刻画一个最优解的结构特征。
递归地定义最优解的值。
计算最优解的值，通常使用自底向上的方法。
利用计算出的信息构造一个最优解。

动态规划的两个要素：最优子结构和子问题重叠。

最优子结构：如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。
子问题重叠：递归算法反复求解相同的子问题，称为最优化问题具有重叠性质。

知道这些还不够，因为难点就是在寻找最优子结构的过程中，以及如何递进地通过子问题推到最终原始问题的最优解。

寻找最优子结构的过程往往如下：

首先做出一个选择，定义这个选择的意义，之后就会产生出一个或多个待解的子问题。
假定已经知道哪种选择才会得到最优解。先并不用关心这种选择是如何得到的。
给定可获得最优解的选择后，确定会产生哪些子问题。尽量保持子问题空间尽可能简单。
利用“剪贴－粘贴”计数证明每个子问题的解就是它本身最优解。

在做选择的时候试试使用“首先”或者“最后”的词语来描述你的选择方法，总是能够帮助我们理解如何更好的选择。

选择的方法不同，最优解子结构也会不同，从而计算方法也不同。下面用戳气球的例子来说明。

https://leetcode.com/problems/burst-balloons/

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

问题分析和解决方法：

class Solution {
    public int maxCoins(int[] nums) {
        //1. coins = nums[left] * nums[i] * nums[right]
        //2. next coin: nums[left] * nums[right] at least another time
        //3. max sum(coins)
        //4. num in nums: 0<=nums[i]<=100
        //5. which one should be burst first?
        //5.2 burst the largest num first?
        //5.1 burst the smallest num first?
        //5.3 burst the one which get coins max first?
        //test case1: 
            //5.1 [1,2,3] => 1*1*2+[2,3]=> 2+1*2*3+[3] =>2+6+3=11
            //5.2 [1,2,3] => [1,2] + 2*3*1 =>[1] + 1*2*1 + 6 =>1+2+6=9
            //5.3 same as 5.2, so at least 5.2 and 5.3 are not right
        //test case2:
            // 5.1 [2,1,3] => 2*1*3 +[2,3] =>6+1*2*3+[3] =>12+3=>15
            // the number order impact the result as well (11!=15)
        //test case3:
            //5.1:[3,6,7] => 18+42+7 < 3*6*7 + 21 + 7 so not 5.1 as well.
        //6. we cannot decide which one should be bursted first directly, no rules.
        //7. Here priorityQueue can help as there is no resort.
        //8. check if we can DP. 
        //9. how about DCC?
        //10. remove one by one so totally nums.length times
            //10.1 if only one num, result is the num
            //10.2 if only two nums, result is a*b + b (b>a)
            //11.3 if only three nums,result will be Coin([a,b,c]) = Max(a*b*c +[a,c], a*b+b*c+max(b,c),a*b+max(a,b)+b*c) 
            //max(a*b*c + a*c + max(a,c), a*b+b*c + max(a,b,c))
            //11.4 append d, there are four nums. Coin([a,b,c,d]) = Max(Coin([a,b,c])+ c*d, Coin(a,b,d)+bcd, ...). this will not calculatable.
        //How about considering which one should be bursted last? this will not impact if the left one and the right one is bursted or not
            //DP[k]? or DP[start][end]
            // dp[numi..numj] = dp[numi..numk] + dp[numk..numj] + numi＊numk*numj. (numi,numj is the border value)
        //dp[numi,numi]=numi
            if(nums==null || nums.length==0) return 0;
            int len=nums.length;
            int[] exNums = new int[len+2];
            int n=1; // non-zero nums
            for(int num:nums){
                if(num!=0)exNums[n++]=num;
            }
            exNums[0]=1;
            exNums[n]=1;
            int[][] dp = new int[n+1][n+1];
            for(int j=2;j<n+1;j++){
                for(int i=j-2;i>=0;i--){
                    for(int k=i+1;k<j;k++){
                        dp[i][j]=Math.max(dp[i][j],dp[i][k]+dp[k][j]+exNums[i]*exNums[k]*exNums[j]);
                    }
                }
            }
            
            return dp[0][n];
    }
}

分析之后使用动态规划解决该问题。在构建最优解的时候如何做假定选择是个问题。

在[i,j]个气球中如果我们假定“首先”戳破第k个气球得到最优解，能够使得我们得到那次获取的金币，但是之后却得不到子问题。
换个思路：在[i,j]个气球中如果我们假定“最后”戳破第k个气球得到最优解，并能够得到子结构[i,k]和［k,j]。这里还有一个难点：[i,j]中的i和j不包含在里面，而是作为左右边界处理。这个就可以得到最后戳破第k个气球时的金币值为 nums[i]*nums[k]*nums[j]，从而子问题是［i,k］和［k,j］而不是[i,k-1]和[k+1,j]。这是关键。
自底向上计算最优解的时候也是有不同的。比较方法一和方法二，找不同。

方法二：

class Solution {
    public int maxCoins(int[] nums) {
        
        int[][] dp = new int[nums.length+2][nums.length+2];
        int[] newnums = new int[nums.length+2];
        int n = newnums.length;
        newnums[0] = 1;
        newnums[n-1] = 1;
        for (int i=1; i<n-1; i++){
            newnums[i] = nums[i-1];
        }
        
        for (int k=2; k<n; k++){
            for (int left = 0; left<n-k; left++){
                int right = left+k;
                for (int i=left+1; i<right; i++){
                    dp[left][right] = Math.max(dp[left][right], dp[left][i]+dp[i][right]+newnums[left]*newnums[i]*newnums[right]);
                }
            }
        }
        return dp[0][n-1]; 
    }
}

第一种方法中第一层循环是j,是坐标。而第二种方法中第一层循环是长度k。所有计算dp[i][j]的顺序是不一样的。

动态规划学习的一点心得

发表评论