动态规划 #

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

509. 斐波那契数 #

题目地址：https://leetcode-cn.com/problems/fibonacci-number/

解法1：递归

解法2：动态规划，一维数组

解法3：动态规划，状态压缩缩

70. 爬楼梯 #

题目地址：https://leetcode-cn.com/problems/climbing-stairs/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

746. 使用最小花费爬楼梯 #

题目链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs/

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

62.不同路径 #

题目链接：https://leetcode-cn.com/problems/unique-paths/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

63. 不同路径 II #

题目链接：https://leetcode-cn.com/problems/unique-paths-ii/

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

• 条件：遇到障碍dp[i][j]保持0就可以了。

343. 整数拆分 #

题目链接：https://leetcode-cn.com/problems/integer-break/

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

• dp[i]: 分拆数字i，可以得到的最大乘积为dp[i]。
• dp[i] = max(j * (i-j), j * dp[i-j])

494. 目标和 #

题目链接：https://leetcode-cn.com/problems/target-sum/

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

474.一和零 #

题目链接：https://leetcode-cn.com/problems/ones-and-zeroes/

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

96.不同的二叉搜索树 #

题目链接：https://leetcode-cn.com/problems/unique-binary-search-trees/

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

• 解法一：递归

  • 递归函数参数：是一个区间[1,n]
  • 以 i 为根节点的数量 = [lo, i -1]的数量 * [i+1, hi]的数量
  • 结束条件：为空！没有元素

• 解法二：动态规划

  • dp[i]: 给定i,能组成的不同二叉搜索树的个数
  • 涉及到累加：需要 j 循环
  • dp[i] = 以 j 为头节点，左子树的数量（即dp[j-1]) * 以 j 为头节点，右子树的数量（即dp[i - j])， 即：dp[i] += dp[j-1] * dp[i - j]
  • dp[0] = 1的含义：没有元素的时候，也是一种

• 重叠子问题、最优子结构（子问题互相独立）、状态转移方程

  • 明确「状态」
  • 定义 dp 数组/函数的含义
  • 明确「选择」
  • 明确 base case。

最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到那种恶心人的最值题，思路往动态规划想就对了，这就是套路。

动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，不断以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。

找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路，经常刷题的朋友应该能体会。

1. 遍历的过程中，所需的状态必须是已经计算出来的。看 base case

2. 遍历的终点必须是存储结果的那个位置

子序列问题 #

• 一维dp数组
  • 最长递增子序列
    • dp[i]: 以nums[i]为结尾的最长递增子序列的长度
    • 算出所有dp[i]后，再选最大的就好了。即两次选择
    • 有时间看nlgn的解法
    • 二维递增子序列：信封嵌套问题 - labuladong的算法小抄 (gitbook.io)
  • 最大子序和：具有最大和的连续子数组
    • dp数组：dp[i] = 以nums[i]为结尾的最大子数组和/最长递增子序列
    • 将dp[i+1]与dp[i]建立联系
• 二维 dp 数组
  • 涉及两个字符串/数组
    • 最长公共子序列
      • dp函数：dp(s1, i, s2, j)计算s1[i..]和s2[j..]的最长公共子序列长度
      • base case: i == s1.length() || j == s2.length() 空串 0
      • 如果相等/不等几种情况
      • 备忘录
      • 变1：给定字符串s1和s2，使它们相同所需最小步数 - m - lcs + n - lcs
      • 变2：给定字符串s1和s2，使它们相同所需删除字符ascii值最小和
        • 修改base case
        • 修改状态转移部分
    • 编辑距离
      • dp函数：返回子的最小编辑距离
      • base case: i走完或者j走完，直接返回另一个剩下的长度
      • 如果相等，左上角。否则，三选1，三个角
    • 最小路径和
      • dp[i][j] 取决于 dp[i-1][j] dp[i][j-1]
  • 只涉及一个字符串/数组
    • 最长回文子序列的长度
      • 分析要求的结果，想：怎么从已知的结果推出来
      • dp数组定义：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]
      • 得出状态转移
      • 分析base case
      • 画出dp表，确认遍历方向写for循环

背包问题 #

0-1背包问题 #

1. dp[i][j] : 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
2. dp[i] = 不放物品i（dp[i - 1][j]） + 放物品i （dp[i - 1][j - weight[i]]）。即：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
3. 初始化：dp[0][j] = 0； j < weight[0]时，dp[0][j] = 0，else value[0]

一维滚动数组解法：

vector<int> dp(bagWeight + 1, 0);// 初始化
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

1049. 最后一块石头的重量 II #

题目链接：https://leetcode-cn.com/problems/last-stone-weight-ii/

题目难度：中等

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

• 返回值处理：在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的

子集背包问题 #

1. dp[i][j] : 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，为true则刚好装满
2. dp[i] = 不放物品i（dp[i - 1][j] else 放物品i （dp[i - 1][j - weight[i]]）。即：dp[i][j] = if dp[i - 1][j] else dp[i - 1][j - weight[i]] + value[i])
3. 初始化：dp[…][0] = false，dp[0][..] = true. ？

完全背包问题 #

• dp数组定义：使用前i种物品，当前背包容量为j，有dp[i][j]种方法可以装满
  • 要求的 dp[N][amount]
  • base case: dp[0][..] = 0. dp[…][0] = 1
• 状态转移逻辑（索引i-1表示第i个物品）
  1. 不装：dp[i][j] = dp[i-1][j]
  2. 装：dp[i][j] = dp[i][j-coins[i-1]]

518. 零钱兑换 II #

链接：https://leetcode-cn.com/problems/coin-change-2/

难度：中等

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

• dp[j]：凑成总金额j的组合数为dp[j]

• dp[j] += dp[j - coins[i]];

• 初始化：dp[0] = 1

贪心算法 #

暴力：指数级

动态规划：多项式

贪心：线性

• 最多有多少个无重叠区间
  • 有空看下动归的解法 状态压缩技巧
• 本质就是投影 - 用于base case
• 直接去掉i维，然后分析对应原来的哪一个。分析外层/内层for循环。本质也是投影