第九章 动态规划part13

•  300.最长递增子序列 

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

  思路：该题为典型的动态规划题目，首先要明确dp数组的含义，dp数组表示结尾为nums[i]的最大子序列，因此递推公式就是要求比i小的dp数组+1和dp[i]的max值。

•  674. 最长连续递增序列 

  class Solution {
      public int findLengthOfLCIS(int[] nums) {
          int[] dp = new int[nums.length];
          Arrays.fill(dp,1);
          int result = 1;
          for(int i = 1 ; i < nums.length ; i++){
              if(nums[i] > nums[i-1]){
                  dp[i] = dp[i-1]+1;
              }
              result = Math.max(result, dp[i]);
          }
          return result;
      }
  }

  思路：该题与上一题类似，是上一题的特殊情况，必须为连续的递增子序列，所以只需要和前一个nums比较。也可以使用贪心算法解题。

•  718. 最长重复子数组  

  // 版本一
  class Solution {
      public int findLength(int[] nums1, int[] nums2) {
          int result = 0;
          int[][] dp = new int[nums1.length + 1][nums2.length + 1];
          
          for (int i = 1; i < nums1.length + 1; i++) {
              for (int j = 1; j < nums2.length + 1; j++) {
                  if (nums1[i - 1] == nums2[j - 1]) {
                      dp[i][j] = dp[i - 1][j - 1] + 1;
                      result = Math.max(result, dp[i][j]);
                  }
              }
          }
          
          return result;
      }
  }

  思路：确定dp数组，dp数组表示i-1，j-1的最长重复子数组，关键是表示i-1和j-1的子数组。然后就确定递推公式，遍历nums1和nums2，如果相等的话，就在i-1、j-1的基础上加1，用result保存最长的公共子数组。