动态规划

开启了动态规划刷题模块，动态规划的关键是写出状态方程和确定边界，从易到难开启练级之路。

在什么情况下用到动态规划

一维/二维

LCP 19. 秋叶收藏集（待完成

先是四个简单题入门

leetcode509 斐波那契数

leetcode1137 第n个泰波那契数

leetcode70 爬楼梯计数问题

leetcode746 使用最小花费爬楼梯最优问题

509算是最基础的递归，1137使用递归会超时，从官方解答中学到了滚动数组的解法。滚动数组可以将二维降为一维。

70算是一个典型的动态规划，登顶的情况可以分为最后一级台阶为1或为2，自然可以写出状态方程，dp[n] = dp[n-1] + dp[n-2]，同样可以使用滚动数组的方式减少内存占用，解决超时问题。746是70的变体，可以选择从下标为0或1的元素作为初始阶梯，状态方程可以写为dp[i] = min(dp[i - 1]+ costs[i - 1], dp[i - 2] + costs[i - 2]);

leetcode198 打家劫舍

leetcode213 打家劫舍II

一维，打家劫舍这两个题，偷第k家，最大收益dp[k-2]+nums[k]，不偷第k家，最优收益就是偷前一家的最大收益dp[k-1]

213同样可以使用滚动数组来降低空间复杂度。

213是198的变体，题解中有一个使用两次贪心算法求解的，没太理解。

dp1[1] = nums[0];
   dp2[1] = nums[1];
   for(int i=2; i < n; i++){
       dp1[i] = Math.max(dp1[i - 2]+nums[i -1], dp1[i - 1]);
       dp2[i] = Math.max(dp2[i - 2]+nums[i], dp2[i - 1]);
   }

leetcode740 删除并获取数先做散列再做打家劫舍

leetcode 53 最大子数组和这道题竟然是简单难度。拿到题的思路是暴力解法和动态规划，但是状态方程着实被难住了，作为新手还是要积累经验。

f(i) 表示以 i 元素为结尾的连续数组的最大和。

考虑到 f(i)只和 f(i-1)相关，可以只用一个变量 pre 来维护对于当前 f(i) 的 f(i-1)的值是多少，从而让空间复杂度降低到 O(1)，这有点类似「滚动数组」的思想。

LeetCode-Solution

leetcode 918 环形子数组的最大和这题分两种情况，第一种最大和数组不是环，第二种最大和数组涉及环。题解的图很清楚，关键是对于第二种情况的理解。接下来的解法类似于53最大子数组之和。

leetcode152 乘积最大子数组感觉上和最大连续子数组和是一个类型。但实际上有区别。记录乘积为正的最大和乘积为负的最小连续子数组大小。

leetcode 1567 乘积为正数的最长子数组长度我是废物.jpg，类似于152题，记录最长乘积正数数组长度和最长乘积负数长度。

调试真心好用==正式上机不知道有没有调试功能

leetcode 1014 最佳观光组合暴力解法果然超时了，O(n^2)能过的数据规模大概在1000左右。MARK！一边遍历一边计算最大值。数学思维值得学习。

139. 单词拆分字符串s.substring()用法。定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i-1]是否能被空格拆分成若干个字典中出现的单词。对于字符串 s[0..i-1]的分割点 j，前j个字母已经判断过，只需要判断[j, i]是否在字典中。从而形成了重叠子问题。

413. 等差数列划分以nums[i]作为结尾的等差数列，答案增加的次数 t_i, 如果到i+1也满足等差数列，
$$
t_{i+1} = t_i + 1
$$
若不满足等差队列则t = 0

42. 接雨水这是一道困难题，（待完成。

91. 解码方法（待完成

最xx序列/串

当题目和序列或者字符串相关时，可以考虑把状态设计成下面两种形式：

令dp[i]表示以A[i]结尾的xxx
令dp[i][j]表示A[i]到A[j]区间的xxx

300. 最长递增子序列一维

for(int i = 1; i < n; i++){
    dp[i] = 1;
    for(int j = 0; j < i; j++){
        if(nums[i] > nums[j]){
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    max = Math.max(max, dp[i]);
}

1143. 最长公共子序列二维，dp[i][j]代表text1的 i 位前和text2的 j 位前最长公共子序列。

516. 最长回文子序列二维，子序列通常是不连续的，而子串通常是连续的。 dp[i][j]表示字符串s的下标范围[i, j] 内的最长回文子序列长度。

int n = s.length();
int[][] dp = new int[n][n];

for(int i = n - 1; i >= 0; i--){
    dp[i][i] = 1;
    for(int j = i + 1; j < n; j++){
        if(s.charAt(i) == s.charAt(j)){
            dp[i][j] = dp[i + 1][j - 1] + 2;
        }else{
            dp[i][j] = Math.max(dp[i+1][j], dp[i][j - 1]);
        }
    }
}

为什么要逆序遍历？

因为状态转移式里面需要用到 dp[i+1] （或dp[j-1]），所以在遍历到 i,j 的时候，诸如 i+1,j-1 这些点，是应该需要已经访问过了的（否则未访问过的点，dp就成初始值 0 了）所以 i 要逆序遍历，j 要正序遍历

5. 最长回文子串二维，动态规划。意外的卡了很久，是因为边界条件赋值错了，可恶。按照长度递归。

        int n = s.length();
        int[][] dp = new int[n][n];
        int maxLen = 1;
        int begin = 0;
        for(int i = 0; i < n; i++){
            dp[i][i] = 1;
            if(i < n - 1 && s.charAt(i) == s.charAt(i + 1)){
                dp[i][i + 1] = 1;
                maxLen = 2;
                begin = i;
            }
        }
//计算dp[0][4]时，将会转化为dp[1][3]，并不是初始化过的值。对枚举顺序调和也无法解决这个问题，则换个思路
//根据递推写法从边界出发的原理，注意到边界问题是字串长度为1和2的字串，每次转移时都是对字串长度剪了1，不妨从子串长度和枚举子串初始位置进行枚举
		//子串长度
        for(int L = 3; L <= n; L++){
            //枚举初始位置
            for(int i = 0; i + L - 1 < n; i++){
                int j = i + L -1;
                if(s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1] == 1){
                    dp[i][j] = 1;
                    maxLen = L;
                    begin = i;
                }

            }
        }

392. 判断子序列

376. 摆动序列

路径问题

64. 最小路径和二维，比想象的简单，每次只能向下或者向右一步，本来以为要有个directions数组，逐个方向枚举，好像不需要。dp[i][j]表示当前位置的最小路径和。

      int rows = grid.length, columns = grid[0].length;
      int[][] dp = new int[rows][columns];
//边界
      dp[0][0] = grid[0][0];
      for(int i = 1; i < rows; i++){
          dp[i][0] = dp[i - 1][0] + grid[i][0];
      }
      for(int j = 1; j < columns; j++){
          dp[0][j] = dp[0][j - 1] + grid[0][j];
      }
//状态转移
      for(int i = 1; i < rows; i++){
          for(int j = 1; j < columns; j++){
              dp[i][j] = Math.min(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j]);
          }
      }

      return dp[rows - 1][columns - 1];

62. 不同路径二维，小case，和上一个问题基本一样。

63. 不同路径 II 在上一题的基础上多了一个判断。看了官解有更简洁的写法，可以通过滚动数组优化。因为f(i, j)只与f(i - 1, j)和f(i, j -1)有关，可以用滚动数组的思想简化空间复杂度。

「滚动数组思想」是一种常见的动态规划优化方法，在我们的题目中已经多次使用到，例如「剑指 Offer 46. 把数字翻译成字符串」、「70. 爬楼梯」等，当我们定义的状态在动态规划的转移方程中只和某几个状态相关的时候，就可以考虑这种优化方法，目的是给空间复杂度「降维」。

作者：LeetCode-Solution

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。

优化的代码：

int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[] dp = new int[n];
if(obstacleGrid[0][0] == 0) {
    dp[0] = 1;
}

for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
        if(obstacleGrid[i][j] == 1){
            dp[j] = 0;
            continue;
        }
        if(j - 1 >= 0){
            dp[j] += dp[j - 1];
        }                
    }
}

931. 下降路径最小和

一维即可解决。注意调整枚举顺序，状态转移方程中
$$
matrix[i][j] = min(matrix[i + 1][j], matrix[i + 1][j - 1],matrix[i+ 1][j + 1]) + matrix[i][j];
$$
与第 i + 1 项有关。

120. 三角形最小路径和

也是非常相似的题。可以二维降一维。
$$
ans[j] = Math.min(ans[j], ans[j + 1])+ triangle.get(i).get(j);
$$
221. 最大正方形

背包问题

416. 分割等和子集 dp[i][j]的含义很重要。

boolean[][] dp = new boolean[n][target + 1];//前[0, i]个数选取和等于target，target+1是考虑到和为0
//边界
for(int i = 0; i < n; i++){
    dp[i][0] = true;
}
dp[0][nums[0]] = true;

for(int i = 1; i < n; i++){
    int num = nums[i];
    for(int j = 1; j <= target; j++){
        if(num < j){
            //选或不选
            dp[i][j] = dp[i - 1][j]|dp[i - 1][j - num];
        }else{
            dp[i][j] = dp[i - 1][j];
        }
    }
}

return dp[n - 1][target];

494. 目标和本以为会是和416分割等和子集差不多的题。状态转移方程很容易想到，卡在了dp数组的定义。看了评论区的解释豁然开朗。采用倒序的原因mark一下。

/* 原问题等同于： 找到nums一个正子集P和一个负子集N，使得总和等于target。即sum - sum(N) == sum(P)
即sum(P) - sum(N) == target, sum - sum(N) - sum(N) = target
即2 * sum(N) = sum - target; sum - target必须>=0的偶数。换位sum(P)同理。

即2 * sum(P) == target + sum(nums)， 其中target + sum(nums)必须>=0且为偶数，否则等式不可能成立。
则问题转换为：存在多少个子集P，使sum(N) == (sum - target)/2。*/

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num: nums){
            sum += num;
        }
        int diff = sum - target;
        if(diff < 0 || diff % 2 != 0)   return 0;
        int neg = diff / 2;

        int[] dp = new int[neg + 1];//考虑和为0
        dp[0] = 1;
        for(int num : nums){
            //实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是dp[i−1][] 中的元素值。
            for(int j = neg; j >= num; j--){
                dp[j] = dp[j] + dp[j - num];
            }
        }
        return dp[neg];
    }

解法二回溯（算是加入target的集合类吧）。

1049. 最后一块石头的重量 II 跪了。和上一题一样怎么想到是背包问题有点难。理解题意，简单来说就是任意选i块石头，使得他们的重量趋近于总重量的一半，因为这样和另一半抵消的差值就是最小的（From Eason同学）。是目标和的变体。

474. 一和零三维01背包问题，dp[i][j][k]三维数组来表示字符串前i个字符串中使用j个0和k个1最多得到的子集个数。方法二可以使用滚动数组降低维度。

===================手动分割线=====================

补充一个背包问题汇总：

01背包：416. 分割等和子集 474. 一和零 494. 目标和 879. 盈利计划 1049. 最后一块石头的重量 II 1230. 抛掷硬币

完全背包：1449. 数位成本和为目标值的最大数字 322. 零钱兑换 518. 零钱兑换 II 279. 完全平方数

518. 零钱兑换 II 典型的完全背包问题。每个元素可以重复选取，且不考虑选取的顺序，组合问题。dp[i]表示金钱和为i的硬币组合数。第一层循环是遍历coins，确定的顺序不会出现重复的排列。第二层循环从coin开始遍历到amount，mark学习。

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        //以当前coin为结尾的且和为i
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

377. 组合总和 Ⅳ 和上一题相似，完全背包问题。最开始的想法是回溯。每个元素可以重复选取，不同的是这题中需要考虑选取元素的顺序，排列问题。

322. 零钱兑换 dp[i]表示金钱和为i的最少个数。 Arrays.fill(dp, max)

279. 完全平方数 dp[i] 表示和为i的完全平方数的最小数量。 Arrays.fill(dp, Integer.MAX_VALUE); 和上一题很像。

70. 爬楼梯终于遇到一个简单题。还是做过的。可以用滚动数组的思想优化空间复杂度。

股票问题

121. 买卖股票的最佳时机这题可以暴力解也可以借鉴1014，将双重循环转变为单层循环，用动态规划解。难得自己解出来。

122. 买卖股票的最佳时机 II 这题看了题解才发现好简单，我自己搞复杂了。算在贪心里更合适，动态规划大材小用。可以先购买然后同一天出手，分为两种情况，当前持有股票和不持有股票，dp[i][0]表示不持有股票，前i天的最大利润，dp[i][1]表示持有股票，前i天的最大利润。

dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++){
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}

123. 买卖股票的最佳时机 III 限定最多完成两笔交易。

int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for(int i = 1; i < n; i++){
    buy1 = Math.max(buy1, -prices[i]);
    sell1 = Math.max(sell1, buy1 + prices[i]);
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, buy2 + prices[i]);
}

188. 买卖股票的最佳时机 IV **这几个股票问题里最复杂的一个了吧。上一题的升级版，限定最多完成k笔交易。类似的我们用一系列变量存储【买入】的状态，再用一系列变量存储【卖出】的状态。官解有点难以理解，参考了讨论区的题解。

int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
Arrays.fill(buy, -prices[0]);
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= k; j++) {
        buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
        sell[j] = Math.max(sell[j], buy[j] + prices[i]);
    }
}
return sell[k];

股票问题思路

我们用 buy[i][j]表示对于数组 prices[0..i] 中的价格而言，进行恰好 j 笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用sell[i][j]表示恰好进行 j 笔交易，并且当前手上不持有股票，这种情况下的最大利润。

作者：LeetCode-Solution

309. 最佳买卖股票时机含冷冻期

f[0][0] = -prices[0];//持有股票
f[0][1] = 0;//未持有股票，冷冻期
f[0][2] = 0;//未持有股票，非冷冻期
for(int i = 1; i < n; i++){
    f[i][0] = Math.max(f[i - 1][0], f[i -1][2]- prices[i]);
    f[i][1] = f[i - 1][0] + prices[i];
    f[i][2] = Math.max(f[i - 1][2], f[i - 1][1]);
}

714. 买卖股票的最佳时机含手续费和122. 买卖股票的最佳时机 II 的唯一区别在于有咩有手续费。有了前面的基础好写很多。

dp[0][0] = 0;//不持有股票
dp[0][1] = -prices[0] - fee;//持有股票
for(int i = 1; i < n; i++){
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] -fee);
}

记忆化搜索

记忆化搜索=搜索的形式+动态规划的思想。记忆化搜索是类似于动态规划的，不同的是，它是倒做的“递归式动态规划”。

from：记忆化搜索专题