image.png
image.png
image.png

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

image.png

1.基础题目

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n ，请计算 F(n) 。 示例 1： 输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

image.png

  1. class Solution {
  2.     public int fib(int n) {
  3.         if(n < 2) return n;
  4.         int[] dp = new int[n + 1];
  5.         dp[0] = 0;
  6.         dp[1] = 1;
  7.         for(int i = 2; i <= n; i++){
  8.             dp[i] = dp[i - 1] + dp[i - 2];
  9.         }
  10.         return dp[n];           //时间复杂苏：O(n)
  11.     }                           //空间复杂苏：O(n)
  12. }
  14. class Solution{
  15.     public int fib(int n){
  16.         if(n == 0) retrun 0;
  17.         int a = 0;
  18.         int b = 1;
  19.         int sum = 0;
  20.         for(int i = 0; i < n; i++){
  21.             sum = (a + b);
  22.             a = b;
  23.             b = sum;
  24.         }
  25.         return a;              //时间复杂苏：O(n)
  26.     }                          //空间复杂苏：O(1)
  27. }

70. 爬楼梯(青蛙跳台)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。

示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶 示例 2：

输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

image.png

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         if(n == 0 || n == 1) return 1;
  4.         if(n == 2) return 2;
  6.         int[] dp = new int[n + 1]; //防止数组下标越界
  7.         dp[1] = 1;
  8.         dp[2] = 2;
  9.         for(int i = 3; i <= n; i++){
  10.             dp[i] = dp[i - 1] + dp[i - 2];
  11.         }
  12.         return dp[n];
  13.     }
  14. }
  16. class Solution{
  17.     public int climbStairs(int n){
  18.         if(n <= 2) return n;
  19.         int a = 1, b = 2, sum = 0;
  21.         for(int i = 3; i <= n; i++){
  22.             sum = a + b;
  23.             a = b;
  24.             b = sum;
  25.         }
  26.         return b;
  27.     }
  28. }

746. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1： 输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。 示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

image.png

  1. class Solution {
  2.     public int minCostClimbingStairs(int[] cost) {
  3.         if (cost == null || cost.length == 0) {
  4.             return 0;
  5.         }
  6.         if (cost.length == 1) {
  7.             return cost[0];
  8.         }
  9.         int[] dp = new int[cost.length];
  10.         dp[0] = cost[0];
  11.         dp[1] = cost[1];
  12.         for (int i = 2; i < cost.length; i++) {
  13.             dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
  14.         }
  15.         //最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
  16.         return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
  17.     }
  18. }

62. 不同路径

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

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

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

示例 1： 输入：m = 3, n = 7 输出：28

示例 2： 输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

image.png
image.png

  1. /**
  2.      * 1. 确定dp数组下表含义 dp[i][j] 到每一个坐标可能的路径种类
  3.      * 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1]
  4.      * 3. 初始化 dp[i][0]=1 dp[0][i]=1 初始化横竖就可
  5.      * 4. 遍历顺序 一行一行遍历
  6.      * 5. 推导结果 。。。。。。。。
  7.      *
  8.      * @param m
  9.      * @param n
  10.      * @return
  11.      */
  12. class Solution {
  13.     public int uniquePaths(int m, int n) {
  14.         int[][] dp = new int[m][n];
  15.         //初始化
  16.         for (int i = 0; i < m; i++) {
  17.             dp[i][0] = 1;
  18.         }
  19.         for (int i = 0; i < n; i++) {
  20.             dp[0][i] = 1;
  21.         }
  23.         for (int i = 1; i < m; i++) {
  24.             for (int j = 1; j < n; j++) {
  25.                 dp[i][j] = dp[i-1][j]+dp[i][j-1];
  26.             }
  27.         }
  28.         return dp[m-1][n-1];
  29.     }
  30. }

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

image.png

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int n = obstacleGrid.length, m = obstacleGrid[0].length;
  4.         int[][] dp = new int[n][m];
  5.         dp[0][0] = 1 - obstacleGrid[0][0];
  6.         for (int i = 1; i < m; i++) {
  7.             if (obstacleGrid[0][i] == 0 && dp[0][i - 1] == 1) {
  8.                 dp[0][i] = 1;
  9.             }
  10.         }
  11.         for (int i = 1; i < n; i++) {
  12.             if (obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1) {
  13.                 dp[i][0] = 1;
  14.             }
  15.         }
  16.         for (int i = 1; i < n; i++) {
  17.             for (int j = 1; j < m; j++) {
  18.                 if (obstacleGrid[i][j] == 1) continue;
  19.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  20.             }
  21.         }
  22.         return dp[n - 1][m - 1];
  23.     }
  24. }

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2:

输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

image.png

  1. class Solution {
  2.     public int integerBreak(int n) {
  3.         //dp[i]为正整数i拆分结果的最大乘积
  4.         int[] dp = new int[n+1]; 
  5.         dp[2] = 1;
  6.         for (int i = 3; i <= n; ++i) {
  7.             for (int j = 1; j < i - 1; ++j) {
  8.                 //j*(i-j)代表把i拆分为j和i-j两个数相乘
  9.                 //j*dp[i-j]代表把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与j相乘
  10.                 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
  11.             }
  12.         }
  13.         return dp[n];
  14.     }
  15. }

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 输入：n = 3 输出：5 示例 2： 输入：n = 1 输出：1

image.png

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         //初始化 dp 数组
  4.         int[] dp = new int[n + 1];
  5.         //初始化0个节点和1个节点的情况
  6.         dp[0] = 1;
  7.         dp[1] = 1;
  8.         for (int i = 2; i <= n; i++) {
  9.             for (int j = 1; j <= i; j++) {
  10.                 //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
  11.                 //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
  12.                 dp[i] += dp[j - 1] * dp[i - j];
  13.             }
  14.         }
  15.         return dp[n];
  16.     }
  17. }

2. 背包问题

image.png

01背包问题

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例 1：

输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2：

输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。

image.png

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         if(nums == null || nums.length == 0) return false;
  4.         int n = nums.length;
  5.         int sum = 0;
  6.         for(int num : nums){
  7.             sum += num;
  8.         }
  9.         //总和为奇数，不能平分
  10.         if(sum % 2 != 0) return false;
  11.         int target = sum / 2;
  12.         int[] dp = new int[target + 1];
  13.         for(int i = 0; i < n; i++){
  14.             for(int j = target; j >= nums[i]; j--){
  15.                 //物品 i 的重量是 nums[i]，其价值也是 nums[i]
  16.                 dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
  17.             }
  18.         }
  19.         return dp[target] == target;
  20.     }
  21. }

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

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

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

例 1： 输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。 示例 2：

输入：stones = [31,26,33,21,40] 输出：5

image.png

  1. class Solution {
  2.     public int lastStoneWeightII(int[] stones) {
  3.         int sum = 0;
  4.         for (int i : stones) {
  5.             sum += i;
  6.         }
  7.         int target = sum >> 1;
  8.         //初始化dp数组
  9.         int[] dp = new int[target + 1];
  10.         for (int i = 0; i < stones.length; i++) {
  11.             //采用倒序
  12.             for (int j = target; j >= stones[i]; j--) {
  13.                 //两种情况，要么放，要么不放
  14.                 dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
  15.             }
  16.         }
  17.         return sum - 2 * dp[target];
  18.     }
  19. }

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ： 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1：

输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3

示例 2： 输入：nums = [1], target = 1 输出：1

image.png

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         int sum = 0;
  4.         for (int i = 0; i < nums.length; i++) sum += nums[i];
  5.         if ((target + sum) % 2 != 0) return 0;
  6.         int size = (target + sum) / 2;
  7.         if(size < 0) size = -size;
  8.         int[] dp = new int[size + 1];
  9.         dp[0] = 1;
  10.         for (int i = 0; i < nums.length; i++) {
  11.             for (int j = size; j >= nums[i]; j--) {
  12.                 dp[j] += dp[j - nums[i]];
  13.             }
  14.         }
  15.         return dp[size];
  16.     }
  17. }

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。 其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。 示例 2：

输入：strs = [“10”, “0”, “1”], m = 1, n = 1 输出：2 解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

image.png

  1. class Solution {
  2.     public int findMaxForm(String[] strs, int m, int n) {
  3.         //dp[i][j]表示i个0和j个1时的最大子集
  4.         int[][] dp = new int[m + 1][n + 1];
  5.         int oneNum, zeroNum;
  6.         for (String str : strs) {
  7.             oneNum = 0;
  8.             zeroNum = 0;
  9.             for (char ch : str.toCharArray()) {
  10.                 if (ch == '0') {
  11.                     zeroNum++;
  12.                 } else {
  13.                     oneNum++;
  14.                 }
  15.             }
  16.             //倒序遍历
  17.             for (int i = m; i >= zeroNum; i--) {
  18.                 for (int j = n; j >= oneNum; j--) {
  19.                     dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
  20.                 }
  21.             }
  22.         }
  23.         return dp[m][n];
  24.     }
  25. }

完全背包问题

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。

示例 1： 输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2：

输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。

image.png

  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         //递推表达式
  4.         int[] dp = new int[amount + 1];
  5.         //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
  6.         dp[0] = 1;
  7.         for (int i = 0; i < coins.length; i++) {
  8.             for (int j = coins[i]; j <= amount; j++) {
  9.                 dp[j] += dp[j - coins[i]];
  10.             }
  11.         }
  12.         return dp[amount];
  13.     }
  14. }

3. 打家劫舍问题