力扣hot100二刷——动态规划
第二次刷题不在idea写代码，而是直接在leetcode网站上写，“逼”自己掌握常用的函数。
| 标志 | 掌握程度 | 解释 | 办法 |
|---|---|---|---|
| ⭐ | Fully 完全掌握 | 看到题目就有思路，编程也很流利 | |
| ⭐⭐ | Basically 基本掌握 | 需要稍作思考，或者看到提示方法后能解答 | |
| ⭐⭐⭐ | Slightly 稍微掌握 | 需要看之前写过的代码才能想起怎么做 | 多做 |
| ⭐⭐⭐⭐ | absolutely no 完全没有掌握 | 需要看题解才知道怎么做 | 背 |
| ⭐⭐⭐⭐⭐ | 有难度的高频题 | 需要看题解才知道怎么做，而且过几天就忘了这道题怎么做了 | 背背 |
| 77 | ⭐ | 贪心算法 | 121.买卖股票的最佳时机 | 遍历数组，每次都计算、更新ans if(prices[i] > in) { out = prices[i]; ans = Math.max(out - in, ans); } else { in = prices[i]; } | |
|---|---|---|---|---|---|
| 78 | ⭐⭐⭐ | 贪心算法 | 55.跳跃游戏 | 维护一个maxIndex记录最大可以覆盖到的索引 遍历数组，如果当前索引 < maxIndex则更新maxIndex Math.max(i + nums[i], maxIndex) 遍历结束后根据maxIndex的大小返回值 | |
| 79 | ⭐⭐⭐ | 贪心算法 | 45.跳跃游戏2 | 在上一题的基础上改，维护一个end变量来表示当前跳跃次数的覆盖边界 每次遍历中都要判断当前索引是否是边界，是的话表示当前可跳跃的范围已遍历完，跳跃次数ans++ 易错点：循环判断条件不是i < nums.length，而是i < nums.length - 1 | |
| 80 | ⭐⭐⭐⭐ | 贪心算法 | 763.划分字母区间 | 错误的思路：用一个map统计字符出现次数，再次遍历数组，遇到次数变为0的字符就分割一次 正确思路： 统计每个字符最远的距离， 遍历数组并统计目前所有字符的最远距离， 当遍历索引等于当前最远距离时分割 | |
| 81 | ⭐ | Easy | 动态规划 | 70.爬楼梯 | dp[i] = dp[i - 1] + dp[i - 2]; |
| 82 | ⭐⭐ | Easy | 动态规划 | 118.杨辉三角 | 这道题的难点在于集合的运用和添加元素的位置 要注意前一个子集合和后一个子集合的运用 List cur = new ArrayList<>(pre); for(int j = 1; j < i; j++) { cur.set(j, pre.get(j) + pre.get(j - 1)); } cur.add(1); ans.add(new ArrayList<>(cur)); pre = cur; |
| 83 | ⭐⭐ | Medium | 动态规划 | 198.打家劫舍 | dp[i]表示前i间屋子偷到的最大金额，有偷第i 家屋子和不偷第i家屋子两种情况 dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); |
| 84 | ⭐⭐⭐⭐ | Medium | 动态规划 | 279/完全平方数 | 思路： 维护一个数组表示从 前 i 个 整数 中 选出 完全平方和 为 j 的完全平方数的最少个数 由题目中 完全平方数的范围可知，整数的范围是 1 ≤ i ≤ 100 因为这道题 的 所有算例之间 其实可以相互作用，所以 核心代码 都加上 static修饰符 用 static 修饰 代码块，初始化数组中所有值 为 -1 定义一个递归函数，dfs(i, j) 表示 从 前 i 个数中 选出 和为 j 的完全平方数的最少个数 5.1. 如果record[i][j] != -1，直接返回该索引的值 5.2. 如果i == 0，根据 j == 0 的情况，返回 0 或者 Integer.MAX_VALUE 5.3. 如果 i * i > j 返回 dfs(i - 1, j) 5.4. 如果 i + i <= j 返回 dfs(i, j - i * i) + 1 和 dfs(i - 1, j) 中 较小的 遍历过程： 以 3 为例 dfs(1, 3); dfs(1, 2); dfs(1, 1); dfs(1, 0) 【i * i 开始大于 j了】; dfs(0, 0); 以 12 为例 dfs(3, 12); dfs(2, 12); dfs(2, 8) + 1; dfs(2, 4) + 1 + 1; dfs(2, 0)【i * i 开始大于 j了】 + 1 + 1 + 1; dfs(1, 0) + 1 + 1 + 1; dfs(0, 0) + 3; 以 12 为例 dfs(3, 12); dfs(3, 3) + 1; dfs(2, 3) + 1; dfs(1, 3) + 1; dfs(1, 2) + 1 + 1; dfs(1, 1) + 1 + 1 + 1; dfs(1, 0) + 1 + 1 + 1 + 1; dfs(0, 0) + 4; |
| 85 | ⭐⭐⭐ | Medium | 动态规划 | 322/零钱兑换 | dp[i][j] 表示 前 i 个硬币，组成总金额 j 所需要的 最少硬币个数 如果选 第 i 个硬币， dp[i][j] = dp[i][j - coins[i]] + 1; 如果不选 第 i 个硬币， dp[i][j] = dp[i - 1][j]; 选不选 还要看 第 i 个硬币 是否大于 当前金额 |
| 86 | Medium | 动态规划 | 139/单词拆分 | ||
| 87 | ⭐⭐⭐⭐ | Medium | 动态规划 | 300/最长递增子序列 | dp[i] 表示以nums[i] 为结尾的最长递增子序列长度 注意：开始核心代码之前，一定要先给dp数组中每个元素都赋值1，因为最长递增子序列长度至少为1 外层循环遍历数组，表示每个以nums[i] 为结尾的序列 内层循环，从索引0 开始遍历当前序列，遍历过程中根据dp[i] = Math.max(dp[j] + 1, dp[i])来更新dp[i] 内层循环外，外层循环中，还要更新答案ans = Math.max(ans, dp[i])，因为dp[n]并不就是最长递增序列的长度 |
| 88 | ⭐⭐⭐⭐ | Medium | 动态规划 | 152/乘积最大子数组 | 关键在于记录以nums[i]为结尾的子数组的最大乘积 但是由于有负数，所以不仅要记录最大的数max，还要记录最小的数min，因为对于负数来说，乘上一个最小的数可以变成最大的数 如果nums[i]<0，要提前交换max和min的值 更新max，min, ans 返回ans |
| 89 | ⭐⭐⭐⭐ | Medium | 动态规划 | 416.分割等和子集 | 数组可以分割为两个和相同的子集，说明： 数组的和是2的倍数 每个子集的和是数组和的一半 数组长度不能小于2 接下来的做法： 先根据以上要求排除不能分割的情况 初创建dp[i][j]数组，表示前i个数中恰好有和为j的子集，初始化，dp[0][i] 遍历得到dp数组 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]] (j > nums[i]) 返回dp[len - 1][halfSum] |
| 90 | Hard | 动态规划 | 32.最长有效括号 |
图片版：
