300. 最长递增子序列

  1. dp[i] 的含义：在 i 之前，包括 i 的最长递增子序列长度
  2. 转移方程：位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值

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

  1. 初始化：不能设置成0，因为对于每个数来说最少也有自己作为序列的一员，因此应该初始化为1
  2. 遍历顺序：外层遍历数组nums，内层遍历dp，从前向后

674. 最长连续递增序列

  1. dp[i] 的含义：以第i个数为结尾时，最长连续递增序列的长度
  2. 转移方程：dp[i]只和dp[i - 1]有关 如果nums[i] > nums[i - 1]， 则dp[i] = dp[i - 1] + 1
  3. 初始化：dp[i] = 1

718. 最长重复子数组

子序列默认是不要求连续的，子数组连续
子数组问题适合用dp解决

  1. dp[i][j]的含义：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
  2. 状态转移只能从一个方向来，if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1

注意：遍历要从1开始，因此数组空间要多+1；而且循环时是<=；判断条件要将nums1和nums2的下标-1

  1. public int findLength(int[] nums1, int[] nums2) {
  2.     int len1 = nums1.length, len2 = nums2.length;
  3.     int[][] dp = new int[len1 + 1][len2 + 1];
  4.     //dp[0][0] = 0;
  5.     int res = 0;
  6.     for (int i = 1; i <= len1; ++i) {
  7.         for (int j = 1; j <= len2; ++j) {
  8.             if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
  9.             res = Math.max(dp[i][j], res);
  10.         }
  11.     }
  12.     return res;
  13. }

1143. 最长公共子序列

区别在于这里不要求是连续的了

  1. dp[i][j] 的含义：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
  2. 状态转移可以从三个方向

if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

1035. 不相交的线

看出本质

53. 最大子数组和

  1. dp[i] 的含义：包括下标i之前的最大连续子序列和为dp[i]。

  2. 转移方程

    1. for (int i = 1; i < nums.size(); i++) {
    2.  dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
    3.  if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
    4. }

    编辑距离

    两个字符串

    115. 不同的子序列

  3. dp[i][j] ：如果表示为s[0-i] 和t[0-j]均闭区间的子序列个数，那么不能表示s和t空串的情况。所以声明 int[][] dp = new int[m + 1][n + 1]; 这样dp[0][x]可以表示s为空串，dp[x][0]同理。

  4. 怎么想到这样状态方程的？

一点个人经验，见过的很多2个串的题，大部分都是dp[i][j] 分别表示s串[0…i] 和t串[0…j]怎么怎么样 然后都是观察s[i]和t[j]分等或者不等的情况 而且方程通常就是 dp[i-1][j-1] 要么+ 要么 || dp[i-1][j]类似的