知识点

1. 知识点

   1. 最长递增子序列(LIS)

      动态规划的核心设计思想是数学归纳法。设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp[0...i−1] 都已经被算出来了，然后问自己：怎么通过这些结果算出dp[i] ?

      首先要定义清楚 dp 数组的含义，即 dp[i] 的值到底代表着什么。LIS问题中，dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值

      怎么设计算法逻辑来正确计算每个 dp[i] 呢？我们需要正确的状态转移方程。要思考如何进行状态转移，这里就可以使用数学归纳的思想，例如，已经知道了 dp[0...4] 的所有结果，我们如何通过这些已知结果推出 dp[5]，类推到dp[0..i-1]和dp[i]的关系。

      最后，思考base case。LIS中，dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1

   2. LIS算法

       public int LIS(int[] nums) {
           int[] dp = new int[nums.length];
           // base case
           for (int i = 0; i < nums.length; i++) {
               dp[i] = 1;
           }
           // 遍历所有状态
           for (int i = 0; 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);
                   }
               }
           }
      
           int res = 0;
           for (int i = 0; i < nums.length; i++) {
               if (dp[i] > res) res = dp[i];
           }
           return res;
       }

LeetCode算法题

1. LeetCode算法题

   1. 354.【俄罗斯套娃信封问题】

      解题思路：

      先排序，然后对高度使用LIS算法

   2. 300.【最长递增子序列】

      解题思路：

      首先，这是个动态规划可以完成的问题。

      第一步，定义dp数组，这里，定义dp数组为：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

      第二步，使用数学归纳法，找出动态转移方程

      第三步，确定base case， base case：dp[i] 初始值为 1，因为以 nums[i]结尾的最长递增子序列起码要包含它自己。

   3. 53.【最大子序列和】

      解题思路：

      首先，判断是否可以使用滑动窗口来解决，滑动窗口算法就是专门处理子串/子数组问题的。这道题还不能用滑动窗口算法，因为数组中的数字可以是负数，因此扩大窗口和缩小窗口对结果的影响都是不确定的，即扩大窗口可能减小和也可能增大和，缩小窗口同理。

      其次，判断使用动态规划来做

      第一步，定义dp数组。一般是这样定义dp数组：nums[0..i]中的「最大的子数组和」为dp[i]。实际上是不行的，因为子数组一定是连续的，按照我们当前dp数组定义，并不能保证nums[0..i]中的最大子数组与nums[i+1]是相邻的，也就没办法从dp[i]推导出dp[i+1]。重新定义dp数组的含义：以nums[i]为结尾的「最大子数组和」为dp[i]

      第二步，根据数学归纳法，求出状态转移方程。假设我们已经算出了dp[i-1]，如何推导出dp[i]呢？dp[i]有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。同理，对于dp[0..i]和dp[i+1]也适用，状态转移方程正确。

      第三步，确定base case。对于nums[0]，前面没有元素，因此dp[0]=0.

   4. 1143.【最长公共子序列】

      解题思路：

      对于两个字符串求子序列的问题，都是用两个指针i和j分别在两个字符串上移动，大概率是动态规划思路。

      首先，确定dp数组，该dp数组为二维数组，dp[s1.length + 1][s2.length + 1]，因为开始i和j指向-1，即没有进入字符串。

      base case就是，当i和j两个指针指向-1，即还没有开始时，最长公共子序列为0，因此第一行和第一列为都为0。

      状态转移方程，根据i和j的字符等于或不等于的情况来做。

   5. 583.【两个字符串的删除操作】

      解题思路：

      思考一下，最后这两个字符串会被删成什么样子，删除的结果就是它俩的最长公共子序列，因此要计算删除的次数，就可以通过最长公共子序列的长度推导出来