动态规划刷题

https://www.cnblogs.com/kkbill/p/12081172.html
感觉写的真好！

给定一个整数数组nums，找出其中最长递增子序列的长度

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

1、定义状态
dp[i]:以nums[i]为结尾的递增子序列的长度
2、状态转移方程
只要nums[i]严格大于它位置之前的某个数，那么dp[i]=dp[j]+1;
(i是当前数，j是当前数i位置之前的任意一个数，但有可能存在多个大于当前数的数，故dp[i]要实时更新！！)
3、初始化
dp[i]=1;
4、输出
dp数组的最后一个值并不是最长递增子序列的值！！！
dp数组中最大值才是最长递增子序列的值！

public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        //初始化dp数组
        Arrays.fill(dp,1);
        //i表示当前数
        //j表示当前数位置之前的数
        for(int i=1;imax) max=dp[i];
        }
        return max;
    }

给定一个整数数组nums，找出一个具有最大和的连续子数组，返回其最大和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

1、定义状态
dp[i]:以nums[i]为结尾的连续子数组的的最大和。
2、状态转移方程
因为要求是连续子数组，且定义的状态时以当前数为结尾的最大和，所以nums[i]一定会被选上。

若dp[i-1]<=0，nums[i]加上他之后，反而变得更小，故dp[i]=nums[i];若dp[i-1]>0,那么dp[i]=nums[i]+dp[i];

3、初始化
4、输出

public int maxSubArray(int[] nums) {
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        for(int i=1;i0) dp[i]=dp[i-1]+nums[i];
            else dp[i]=nums[i];
        }
        int max=dp[0];
        for(int i=0;imax) max=dp[i];
        }
        return max;
    }

myidea：动态规划就是要找出来环环相扣的那个点，当前的状态要与上一个的状态联系起来。