动态规划

动态规划 #

  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循环。本质也是投影