7._最长递增子数列(以数组下标为核心)

$dp[i] = max(dp[i], dp[j] + 1)$

• 2.18
  • 有点像贪心算法+动态规划
  • 忘记了站木桩，同样需要 j 和 i

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        int maxL = 1;
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            maxL = Math.max(maxL,dp[i]);
        }
        return maxL;
    }
}

• 2.4

  • 这里的 dp 数组的含义是以这个下标为结尾的数字的最长递增子数列，所以需要一个 maxLen 值来保留题目中需要的最长的子数列（不管是以几为结尾）
  • 和6._单词拆分一样有两层 for 循环（j，i），所以这里 dp【i】是会在第二个 for 循环多次更新，需要取最大值
  • 记得初始化填 1

• 12.4

  1. 站在木桩上(i),回头开始数(j),小于木桩就开始更新(状态公式)

• dp[0]也是1,因为dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度

• i也最多到n-1

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int maxLen = 1;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            maxLen = Math.max(maxLen,dp[i]);
        }
        return maxLen;
    }
}

• 注意循环边界
• 如果 dp 数组的下标含义是“金额 / 长度 / 前缀长度”等等范围值， 就要遍历到 ⇐ 目标值。
• “定义结尾，看前驱，比大小，取最大”