DP2

2020-04-09

进一步了解动态规划

再来回顾一下我们之前的那道题：最大连续子序列和

给定一个长度为n的正数序列，求它的最大连续子序列和

比如-2、1、-3、4、-1、2、1、-5、4的最大连续子序列和是4+(-1)+2+1=6

在之前，我们用分治法解过，但那并不是最优解，接下来我们用动态规划的方法实现

状态定义：假设dp(i)是以nums[i]结尾的最大连续子序列和(nums是整个序列)
- 以nums[0] -2结尾的最大连续子序列和即为-2，所以dp[0]=-2
- 以nums[1]1结尾的最大连续子序列和为
- ……
接下来说一下状态转移方程：当我们求得dp[i]的时候，跟dp[i-1]有什么关系呢，这时候我们可以想象，如果此时dp[i-1]是负数的话，我们就不要加上dp[i-1],如果dp[i-1]是正数的话，我们就加上dp[i-1]。这里的dp[i-1]相当于是以nums[i-1]为结尾的最大连续子序列和。

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums==null||nums.length==0) return 0;
      int dp[]=new int [nums.length];
      dp[0]=nums[0];
      int max=dp[0];
		for(int i=1;i<nums.length;i++){
            if(dp[i-1]<=0)
             dp[i]=nums[i];
             else
             //dp[i-1]>0
             dp[i]=dp[i-1]+nums[i];
             max=Math.max(dp[i],max);
        }
        return max;     
	} 
}

通过动态规划的方法，我们成功的将时间复杂度降为了O(n)，此时空间复杂度也为O(n)。

但是，这并不是最优解，我们可以看到此时空间复杂度为O(n)，实际上，在这里我们没有必要开辟一个n个长度的数组。

class Solution {
    public int maxSubArray(int[] nums) {
      if(nums==null||nums.length==0) return 0;
        int dp=nums[0];
       int max=dp;
       for(int i=1;i<nums.length;i++){
           if(dp<0) dp=nums[i];
           else dp+=nums[i];
           max=Math.max(dp,max);
       }
       return max;

    }
}

如果采取这种思路，我们的时间复杂度为O(n),空间复杂度为O(1)。

接下来再举一个栗子

LeetCode 300、最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

假设数组nums[10,2,2,5,1,7,101,18]

dp[i]是以nums[i]结尾的最长上升子序列的长度，初始值为1
故以nums[0]结尾的最长上升子序列为10,dp[0]=1
以nums[1]结尾的最长上升子序列为2,dp[1]=1
以nums[2]结尾的最长上升子序列为2,dp[2]=1
以nums[3]结尾的最长上升子序列为2、5，故dp[3]=2
dp[3]=dp[1]+1=dp[2]+1
……
最长上升子序列的长度是所有dp[i]中的最大值max{dp[i]}

如果像上个问题一样，比如我们要求以7结尾的最长上升子序列时，我们只用看以1结尾的最长上升子序列吗？

明显是不行的，因为往前继续遍历的话，2、5都比7要小，他们都可以构成最长上升子序列。

首先，我们应该比较元素7与之前元素J的大小，如果之前元素J比他大，我们直接跳过就可以了。
如果这个元素J比7小，那么此时dp[7]=dp[j]+1，然后再将j往后移。最后取他们的最大值就可以了

为了方便我们写代码，我们将所有的dp初始值都设为1. （如果我们求以1结尾的最长上升子序列的话，前面的所有元素都要跳过，此时，dp[1]不正好等于1吗？）

当然，状态的初始值dp[0]=1

下面介绍大致的实现思路：

遍历J[0,i)，i是指以他为结尾的最长上升子序列。
如果nums[i]>nums[J]，即代表nums[i]可以接在nums[J]的后面，形成一个较长的上升子序列，即此时dp[i]=dp[J]+1
- dp[i]=max{dp[i],dp[J]+1}
如果nums[i]<=nums[J],我们直接跳过即可。

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null||nums.length==0) return 0;
        
        int dp[]=new int[nums.length];
        int max=dp[0]=1;
        for(int i=1;i<nums.length;i++){
            //初始值默认为1
            dp[i]=1;
            for(int j=0;j<i;j++){
                //直接跳过
             if(nums[i]<=nums[j]) continue;
              else
                //可以连接
              dp[i]=Math.max(dp[i],dp[j]+1);
             
            }
             max=Math.max(max,dp[i]);
        }
return max;
    }
}

不难看出，上述方法所实现的时间复杂度为O(n^2),空间复杂度为O(n)。