动态规划的思考步骤

思考过程

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

基本代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int solover(int n) {
        if(n<=1)return n;
        // 确定dp的含义
        int[]dp=new int[n+1];
        // 对dp数字初始化
        dp[0]=0;
        dp[1]=1;
        // 遍历顺序，利用状态转移方程求解dp数组
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];

    }
}

一维动态规划

leetcode 509 斐波那契数

题目描述

力扣题目链接(opens new window)

斐波那契数，通常用 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

示例 2：

• 输入：3
• 输出：2
• 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

• 输入：4
• 输出：3
• 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

思路解析

• 确定dp数组（dp table）以及下标的含义

  • dp[i]的定义为：第i个数的斐波那契数值是dp[i]

• 确定递推公式

  • 状态转移方程： dp[i] = dp[i - 1] + dp[i - 2];

• dp数组如何初始化

  • 1 2	dp[0] = 0; dp[1] = 1;

• 确定遍历顺序

  • dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，遍历的顺序一定是从前到后遍历的

• 举例推导dp数组

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int fib(int n) {
        if(n<=1)return n;
        // dp[i]为F[i]
        int[]dp=new int[n+1];
        // 初始化
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];

    }
}

leetcode 70 爬楼梯

题目描述

力扣题目链接(opens new window)

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

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

注意：给定 n 是一个正整数。

示例 1：

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

示例 2：

• 输入： 3
• 输出： 3
• 解释： 有三种方法可以爬到楼顶。
  • 1 阶 + 1 阶 + 1 阶
  • 1 阶 + 2 阶
  • 2 阶 + 1 阶

思路解析

• 确定dp数组以及下标的含义

  • dp[i]： 爬到第i层楼梯，有dp[i]种方法

• 确定递推公式

  • 第一种情况：dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶。
  • 第二种情况：dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶。
  • 所以dp[i] = dp[i - 1] + dp[i - 2] 。

• dp数组如何初始化

  • 1 2	dp[0]=1; dp[1]=1;

• 确定遍历顺序：遍历顺序一定是从前向后遍历的

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int climbStairs(int n) {
        // dp[i]为到达第i阶台阶的方式，第n阶为楼顶
        int[]dp=new int[n+1];
        // 初始化
        dp[0]=1;
        dp[1]=1;
        // 状态转移方程:dp[i]=dp[i-1]+dp[i-2]
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

leetcode 746 使用最小花费爬楼梯

题目描述

力扣题目链接

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

思路解析

• 确定dp数组以及下标的含义
  • dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
• 确定递推公式
  • 第一种情况：dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
  • 第二种情况：dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
  • 所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
• dp数组如何初始化
  • 题目描述中明确说明“你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。所以初始化 dp[0] = 0，dp[1] = 0;
• 确定遍历顺序
  • dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组即可

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n=cost.length;
        // dp[i]为到达第i阶台阶的最小花费，第n阶为楼顶
        int[]dp=new int[n+1];
        // 初始化
        dp[0]=0;
        dp[1]=0;
        // 状态转移方程推导
        // 从第i-1阶爬1个台阶:dp[i-1]+cost[i-1]
        // 从第i-2阶爬2个台阶:dp[i-2]+cost[i-2]
        for(int i=2;i<=n;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
}

leetcode 343 整数拆分

题目描述

力扣题目链接(opens new window)

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

示例 1:

• 输入: 2
• 输出: 1
• 解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

• 输入: 10
• 输出: 36
• 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
• 说明: 你可以假设 n 不小于 2 且不大于 58。

思路解析

• 确定dp数组（dp table）以及下标的含义

  • dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

• 确定递推公式

  • 第一种情况：j * (i - j) 直接相乘。单纯的把整数拆分为两个数相乘

  • 第二种情况：j * dp[i - j]，相当于是拆分(i - j)，拆分成两个以及两个以上的个数相乘

  • 递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j})

• dp的初始化

  • 初始化dp[2] = 1=

• 确定遍历顺序

  • 确定遍历顺序，递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
  • i从3开始遍历到n
  • j从1开始遍历到i-1

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int integerBreak(int n) {
        // 分拆数字i可以得到的最大乘积
        int[]dp=new int[n+1];
        // 初始化
        dp[2]=1;
        // 遍历过程
        // 被拆成i*(i-j)
        // 被拆成dp[i-j]*j
        for(int i=3;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],Math.max((i-j)*j,dp[i-j]*j));
            }
        }
        return dp[n];
    }
}

leetcode 96 不同的二叉搜索树

题目描述

力扣题目链接(opens new window)

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

示例:

思路解析

• 确定dp数组（dp table）以及下标的含义

  • dp[i] ： i个不同元素节点组成的二叉搜索树的个数。

• 确定递推公式

  • dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
  • j表示选取的根节点结点的元素，从1遍历到i为止。
    • 左子树：[1,j-1]
    • 右子树：[j+1,i];
  • 所以递推公式：dp[i] += dp[j - 1] * dp[i - j] ; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

• dp数组初始化

  • 初始化dp[0]=1

• 确定遍历顺序

  • 首先遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
  • 那么遍历i里面每一个数作为头结点的状态，用j来遍历。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int numTrees(int n) {
        // dp[i]代表i个节点的不同二叉树数量
        int[]dp=new int[n+1];
        // 初始化
        dp[0]=1;
        // i表示考虑i个节点的情况
        for(int i=1;i<=n;i++){
            // j表示选取的根节点编号
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}

二维动态规划

leetcode 62 不同路径

题目描述

力扣题目链接(opens new window)

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

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

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

示例 1：

• 输入：m = 3, n = 7
• 输出：28

示例 2：

• 输入：m = 2, n = 3
• 输出：3

解释： 从左上角开始，总共有 3 条路径可以到达右下角。

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

示例 3：

• 输入：m = 7, n = 3
• 输出：28

示例 4：

• 输入：m = 3, n = 3
• 输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 10^9

思路解析

• 确定dp数组（dp table）以及下标的含义
  • dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有 dp[i][j] 条不同的路径。
• 确定递推公式
  • dp[i - 1][j] 表示是从(0, 0)的位置到(i - 1, j)有几条路径， dp[i][j - 1] 同理。
  • dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
• dp数组的初始化
  • 首先 dp[i][0] 一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条（竖直向下走），那么 dp[0][j] 也同理（水平向右走。
• 确定遍历顺序
  • 看一下递推公式 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] ，dp[i][j] 都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int uniquePaths(int m, int n) {
        int[][]dp=new int[m][n];
        // 初始化
        // [0,0]到[m,0]的路径只有一条，竖直向下走
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        // [0,0]到[0,n]的路径只有一条，向右走
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        // 转移方程 dp[i[[j]=dp[i-1][j]+dp[i][j-1]
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

leetcode 63 不同路径II

题目描述

力扣题目链接(opens new window)

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

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

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

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

• 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
• 输出：2 解释：
• 3x3 网格的正中间有一个障碍物。
• 从左上角到右下角一共有 2 条不同的路径：
  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

• 输入：obstacleGrid = [[0,1],[0,0]]
• 输出：1

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

思路解析

与上一题的大体思路相同，只是在初始化和遍历过程略有不同。

• 初始化时将遇到障碍物之前的dp数字置为1
• 遍历过程中遇到障碍物跳过该dp数组

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // m行n列
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        int[][]dp=new int[m][n];
        // 初始化
        // 从[0,0]到[i,0]只有一条，遇到障碍物停止
        for(int i=0;i<m&&obstacleGrid[i][0]==0;i++){
            dp[i][0]=1;
        }
        // 从[0,0]到[0,i]只有一条，遇到障碍物停止
        for(int i=0;i<n&&obstacleGrid[0][i]==0;i++){
            dp[0][i]=1;
        }
        //遍历过程
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==1)
                    continue;
                else
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

0-1背包问题

题目描述

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

思路解析

二维dp解法

• 确定dp数组以及下标的含义
  • 有两个维度需要分别表示：物品 和 背包容量
  • dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大
• 确定递推公式
  • 第一种情况：不放物体则 dp[i][j]=dp[i-1][j]
  • 第二种情况：放入物体则 dp[i][j]=dp[i-1][j-weight[i]]+value[i]
  • 取上面的较大值
• dp数组的初始化
  • i=0时
    • j < weight[0]的时候，dp[0][j] 是 0，因为背包容量比编号0的物品重量还小。
    • 当j >= weight[0]时，dp[0][j] 是value[0]
  • j=0时
    • 背包容量为0，dp[i][0]=0
• 确定遍历顺序
  • 先遍历物品再遍历容量，注意判断当背包容量小于物品容量时不放入物品

代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int N=sc.nextInt();
        int[]weight=new int[M];
        int[]value=new int[M];
        for(int i=0;i<M;i++){
            weight[i]=sc.nextInt();
        }
        for(int i=0;i<M;i++){
            value[i]=sc.nextInt();
        }
        // dp[i][j]表示放入[0-i]的物品，背包容量为j的最大价值
        int[][]dp=new int[M][N+1];
        // 初始化
        // 背包空间为0，价值为0
        for(int i=0;i<M;i++){
            dp[i][0]=0;
        }
        // 被背包容量大于weight[0]价值为value[0]
        for(int i=weight[0];i<=N;i++){
            dp[0][i]=value[0];
        }
        for(int i=1;i<M;i++){
            for(int j=1;j<=N;j++){
                if(j<weight[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }
            }
        }
        System.out.println(dp[M-1][N]);
         
    }
}

一维dp解法

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层复制到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

因此可以推出

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

• 确定dp数组的定义
  • dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
• 递推公式
  • 递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
• 初始化
  • 全部初始化为0即可
• 遍历顺序
  • 顺序遍历物品，同时逆序遍历容量
  • 倒序遍历是为了保证物品i只被放入一次 ，从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了

代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int N=sc.nextInt();
        int[]weight=new int[M];
        int[]value=new int[M];
        for(int i=0;i<M;i++){
            weight[i]=sc.nextInt();
        }
        for(int i=0;i<M;i++){
            value[i]=sc.nextInt();
        }
        // dp[j]背包容量为j的最大价值
        int[]dp=new int[N+1];
        for(int i=0;i<M;i++){
            for (int j = N; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[N]);
    }
}

经典例题

板子题：https://kamacoder.com/problempage.php?pid=1046

leetcode 416 分割等和子集

题目描述

力扣题目链接(opens new window)

题目难易：中等

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

• 输入: [1, 5, 11, 5]
• 输出: true
• 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

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

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

思路解析

本题可以将其视为一个0-1背包问题。nums中的数字为重量和价值的物品

既有一个 只能装重量为 sum / 2 的背包，商品为数字，这些数字能不能把 这个背包装满。

即为求解装满 承载重量为 sum / 2 的背包，价值最大是多少？如果最大价值是 sum / 2，说明正好被商品装满了。

• 确定dp数组以及下标的含义
  • 如果背包所载重量为target， dp[target]就是装满 背包之后的总价值，因为 本题中每一个元素的数值既是重量，也是价值，所以，当 dp[target] == target 的时候，背包就装满了。
• 确定递推公式
  • 本题相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
• dp数组如何初始化
  • dp[0]=0
• 遍历顺序与0-1背包相同

注意当sum是一个奇数是不存在该种方式的

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        int target=sum/2;
        int[]dp=new int[target+1];
        for(int i=0;i<nums.length;i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
            if(dp[target]==target){
                return true;
            }
        }
        return dp[target]==target;
    }
}

leetcode 494 目标和

题目描述

力扣题目链接(opens new window)

难度：中等

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

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

示例：

• 输入：nums: [1, 1, 1, 1, 1], S: 3
• 输出：5

解释：

• -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

一共有5种方法让最终目标和为3。

提示：

• 数组非空，且长度不会超过 20 。
• 初始的数组的和不会超过 1000 。
• 保证返回的最终结果能被 32 位整数存下。

思路解析

本题依然可以转换为0-1背包问题，设加法部分为left，减法部分为right

此时问题就转化为，用nums装满容量为left的背包有多少种方法

• 确定dp数组以及下标的含义
  • dp[i]：使用容量为i的包装满，有dp[j]种方法。
• 确定递推公式
  • 不放物品i：即背包容量为j，里面不放物品i，装满有dp[j]中方法。
  • 放物品i： 即：先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[[j - 物品i容量] 种方法。
  • 递推公式：dp[j] = dp[j] + dp[j - nums[i]]
• 遍历顺序：同0-1背包

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        // left+right=sum
        // left-right=target
        // left=(sum+target)/2
        if (Math.abs(target) > sum) return 0;
        if ((target + sum) % 2 == 1) return 0;
        int bagSize=(sum+target)/2;
        int[]dp=new int[bagSize+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=bagSize;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }
}

leetcode 474 一和零

题目描述

力扣题目链接(opens new window)

给你一个二进制字符串数组 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 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 ‘0’ 和 ‘1’ 组成
• 1 <= m, n <= 100

思路解析

本题其实也是一个01背包问题。本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。而重量也是两个维度（0的个数和1的个数）

• 确定dp数组（dp table）以及下标的含义
  • dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
• 确定递推公式
  • dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
  • 然后我们在遍历的过程中，取dp[i][j]的最大值。
  • 递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
• 遍历顺序：倒序遍历m和n，类似0-1背包

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
        int[][]dp=new int[m+1][n+1];
        int oneNum;
        int zeroNum;
        for(String str:strs){
            oneNum=0;
            zeroNum=0;
            for(char ch:str.toCharArray()){
                if(ch=='0'){
                    zeroNum++;
                }else{
                    oneNum++;
                }
            }
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
}

完全背包问题

题目描述

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品可以使用无数次，求解将哪些物品装入背包里物品价值总和最大。

思路解析

二维dp解法

• 确定dp数组以及下标的含义
  • 有两个维度需要分别表示：物品 和 背包容量
  • dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大
• 确定递推公式
  • 第一种情况：不放物体则 dp[i][j]=dp[i-1][j]
  • 第二种情况：放入物体则 dp[i][j]=dp[i][j-weight[i]]+value[i]
  • 取上面的较大值
• dp数组的初始化
  • i=0时
    • j < weight[0] 的时候，dp[0][j] 是 0，因为背包容量比编号0的物品重量还小。
    • 当 j >= weight[0] 时，dp[0][j] 可以一直装物品0，dp[0][j] = dp[0][j - weight[0]] + value[0]
  • j=0时
    • 背包容量为0，dp[i][0]=0
• 确定遍历顺序
  • 先遍历物品再遍历容量，注意判断当背包容量小于物品容量时不放入物品
  • 求解组合数的时候，先遍历物品还是先遍历背包容量不重要
  • 求解排列数的时候，必须先遍历背包再遍历物品

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int v=sc.nextInt();
        int[] weight=new int[n];
        int[] value=new int[n];
        for(int i=0;i<n;i++){
            weight[i]=sc.nextInt();
            value[i]=sc.nextInt();
        }
        int[][]dp=new int[n][v+1];
        // i=0,初始化
        for(int i=weight[0];i<=v;i++){
            dp[0][i]=dp[0][i-weight[0]]+value[0];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<=v;j++){
                if(j<weight[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
                }
            }
        }
        System.out.println(dp[n-1][v]); 
    }
}

一维dp解法

同理0-1背包问题的一维DP解法，递推公式可以转换为 dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

• 确定dp数组的定义
  • dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
• 递推公式
  • 递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
• 初始化
  • 全部初始化为0即可
• 遍历顺序
  • 顺序遍历物品，同时顺序遍历容量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int v=sc.nextInt();
        int[] weight=new int[n];
        int[] value=new int[n];
        for(int i=0;i<n;i++){
            weight[i]=sc.nextInt();
            value[i]=sc.nextInt();
        }
        int[]dp=new int[v+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<=v;j++){
                if(j<weight[i]){
                    dp[j]=dp[j];
                }else{
                    dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
                }
            }
        }
        System.out.println(dp[v]); 
    }
}

经典例题

leetcode 518 零钱兑换II

题目描述

力扣题目链接(opens new window)

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

示例 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。

示例 3:

• 输入: amount = 10, coins = [10]
• 输出: 1

注意，你可以假设：

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

思路解析

本题实际上可以转换为完全背包问题。将总金额视为背包的容量，硬币作为重量和价值相同的物品

• 确定dp数组的含义
  • dp[j]：凑成总金额j的货币组合数为dp[j]
• 确定递推公式
  • 不放硬币：dp[j]
  • 放入硬币：dp[j-coins[i]]
  • dp[j] =dp[j] + dp[j - coins[i]]
• 初始化
  • 装满背包容量为0 的方法是1，即不放任何物品，dp[0] = 1
• 遍历顺序
  • 本题要求解的是组合数，应当先遍历物品再遍历背包容量

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int change(int amount, int[] coins) {
        int n=coins.length;
        int[]dp=new int[amount+1];
        // 初始化
        dp[0]=1;
        // 求组合数先遍历物品再遍历背包容量
        for(int i=0;i<n;i++){
            for(int j=0;j<=amount;j++){
                // 背包比硬币小，只能不放入硬币
                if(j<coins[i]){
                    dp[j]=dp[j];
                }else{
                    dp[j]=dp[j]+dp[j-coins[i]];
                }
            }
        }
        return dp[amount];
    }
}

leetcode 377 组合总和IV

题目描述

力扣题目链接(opens new window)

难度：中等

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

• nums = [1, 2, 3]
• target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

思路解析

本题依然是完全背包问题，将目标正整数视为背包容量，数组中的元素视为重量和价值相同的物品

• 确定dp数组以及下标的含义

  • dp[i]: 凑成目标正整数为i的排列个数为dp[i]

• 确定递推公式

  • dp[i]有两种可能
    • 加入nums[j]即由 dp[i - nums[j]]推导
    • 不加入nums[j]即由dp[i] 推导出来。

• dp数组如何初始化

  • 递推公式dp[i] += dp[i - nums[j]]，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。

• 确定遍历顺序

  • 本题要求的是排列，要求先遍历背包容量再遍历物品

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int n=nums.length;
        // p[i]: 凑成目标正整数为i的排列个数为dp[i]
        int[]dp=new int[target+1];
        dp[0]=1;
        // 求排列数先遍历背包容量再遍历物品
        for(int i=0;i<=target;i++){
            for(int j=0;j<n;j++){
                if(i<nums[j]){
                    dp[i]=dp[i];
                }else{
                    dp[i]=dp[i]+dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}

leetcode 322 零钱兑换

题目描述

力扣题目链接(opens new window)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

• 输入：coins = [1, 2, 5], amount = 11
• 输出：3
• 解释：11 = 5 + 5 + 1

示例 2：

• 输入：coins = [2], amount = 3
• 输出：-1

示例 3：

• 输入：coins = [1], amount = 0
• 输出：0

示例 4：

• 输入：coins = [1], amount = 1
• 输出：1

示例 5：

• 输入：coins = [1], amount = 2
• 输出：2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

思路解析

• 确定dp数组以及下标的含义

  • dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

• 确定递推公式

  • 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i] 即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
  • 递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

• dp数组初始化

  • 凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
  • 其他下标对应的数值，考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

• 遍历过程

  • 本题是求解是组合数（硬币的顺序不重要）

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n=coins.length;
        // 凑足总额为j所需钱币的最少个数为dp[j]
        int[]dp=new int[amount+1];
        // 初始化DP数值
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<=amount;j++){
                if(j<coins[i]){
                    dp[j]=dp[j];
                }else if(dp[j-coins[i]]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}

leetcode 279 完全平方数

题目描述

力扣题目链接(opens new window)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

• 输入：n = 12
• 输出：3
• 解释：12 = 4 + 4 + 4

示例 2：

• 输入：n = 13
• 输出：2
• 解释：13 = 4 + 9

提示：

• 1 <= n <= 10^4

思路解析

完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

• 确定dp数组（dp table）以及下标的含义

  • dp[j]：和为j的完全平方数的最少数量为dp[j]

• 确定递推公式

  • dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
  • dp[j] = min(dp[j - i * i] + 1, dp[j]);

• dp数组如何初始化

  • dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。
  • 非0下标的dp[j]应该是很大的值，从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

• 确定遍历顺序

  • 本题求解的是组合数就是外层for循环遍历物品，内层for遍历背包。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int numSquares(int n) {
        int[]dp=new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j<i*i){
                    dp[j]=dp[j];
                }else{
                    dp[j]=Math.min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
}

leetcode 139 单词拆分

题目描述

力扣题目链接(opens new window)

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

• 输入: s = “leetcode”, wordDict = [“leet”, “code”]
• 输出: true
• 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

示例 2：

• 输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
• 输出: true
• 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
• 注意你可以重复使用字典中的单词。

示例 3：

• 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
• 输出: false

思路解析

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

• 确定dp数组以及下标的含义

  • dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

• 确定递推公式

  • 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
  • 递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

• dp数组如何初始化

  • dp[0]一定要为true，否则递推下去后面都都是false了。
  • 下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

• 确定遍历顺序

  • 本题求的是排列数，先遍历背包再遍历物品

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int m=wordDict.size();
        int n=s.length();
        // 存储字典
        HashSet<String>set=new HashSet<>(wordDict);
        // 长度为i的字符串可以被划分
        boolean[]dp=new boolean[n+1];
        dp[0]=true;
        // 先遍历背包容量（字符串长度）
        // 后遍历物品
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                String str=s.substring(j,j+(i-j));
                if(dp[j]==true&&set.contains(str)){
                    dp[i]=true;
                }
            }
        }
        return dp[n];
    }
}

打劫问题

leetcode 198 打家劫舍

题目描述

力扣题目链接(opens new window)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

• 示例 1：
• 输入：[1,2,3,1]
• 输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

• 示例 2：
• 输入：[2,7,9,3,1]
• 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

思路解析

• 确定dp数组（dp table）以及下标的含义

  • dp[i]：考虑下标[0-i]以内的房屋，最多可以偷窃的金额为dp[i]。

• 确定递推公式

  • 决定dp[i]的因素就是第i房间偷还是不偷。

  • 如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

  • 如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房

  • dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

• dp数组如何初始化

  • 从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]
  • dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值

• 确定遍历顺序

  • dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        // 从[0-i]房间可以偷的最大金额
        int[]dp=new int[n];
        if(n==1)return nums[0];
        // 数值初始化
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

leetcode 213 打家劫舍II

题目描述

力扣题目链接(opens new window)

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

• 输入：nums = [2,3,2]
• 输出：3
• 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
• 示例 2：
• 输入：nums = [1,2,3,1]
• 输出：4
• 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
• 示例 3：
• 输入：nums = [0]
• 输出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

思路解析

对于一个数组，成环的话主要有如下三种情况：

• 考虑不包含首尾元素
• 考虑包含首元素，不包含尾元素
• 考虑包含尾元素，不包含首元素

因此可以将上一题的逻辑封装成方法，然后比较后两者方法的较大值

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int result1=rob(0,nums.length-2,nums);
        int result2=rob(1,nums.length-1,nums);
        return Math.max(result1,result2);


    }
    public int rob(int start,int end,int[]nums){
        if (end == start) return nums[start];
        int n=nums.length;
        int[]dp=new int[n];
        dp[start]=nums[start];
        dp[start+1]=Math.max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[end];
    }
}

股票问题

leetcode 121 买卖股票的最佳时机

题目描述

力扣题目链接(opens new window)

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

• 示例 1：
• 输入：[7,1,5,3,6,4]
• 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
• 示例 2：
• 输入：prices = [7,6,4,3,1]
• 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

思路解析

• 确定dp数组以及下标的含义

  • dp[i][0] 表示第i天持有股票所得最多现金
  • dp[i][1] 表示第i天不持有股票所得最多现金

• 确定递推公式

  • 如果第i天持有股票即 dp[i][0] ， 那么可以由两个状态推出来

    • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]

    • 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

  • 如果第i天不持有股票即 dp[i][1] ， 也可以由两个状态推出来

    • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]

    • 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

• dp数组初始化

  • 递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]) 可以看出基础都是要从 dp[0][0] 和 dp[0][1] 推导出来。
  • dp[0][0] -= prices[0]
  • dp[0][1] 表示第0天不持有股票，不持有股票那么现金就是0，所以 dp[0][1] = 0

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];
        int result = 0;
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[length - 1][1];
    }
}

leetcode 122 买卖股票的最佳时机II

题目描述

力扣题目链接(opens new window)

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 示例 1:
• 输入: [7,1,5,3,6,4]
• 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
• 示例 2:
• 输入: [1,2,3,4,5]
• 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
• 示例 3:
• 输入: [7,6,4,3,1]
• 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

思路解析

与上一题只有递推公式不一样

• 在上一题中因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即 dp[i][0] 一定就是 -prices[i]。
• 而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。、那么第i天持有股票即 dp[i][0]
• 如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i] 。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][]dp=new int[n][2];
        // 初始化
        dp[0][0]=-prices[0];
        dp[0][1]=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]);
        }
        return dp[n-1][1];
    }
}

leetcode 123 买卖股票的最佳时机III

题目描述

力扣题目链接(opens new window)

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 示例 1:
• 输入：prices = [3,3,5,0,0,3,1,4]
• 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。
• 示例 2：
• 输入：prices = [1,2,3,4,5]
• 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
• 示例 3：
• 输入：prices = [7,6,4,3,1]
• 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为0。
• 示例 4：
• 输入：prices = [1] 输出：0

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5

思路解析

关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

接来下我用动态规划五部曲详细分析一下：

• 确定dp数组以及下标的含义

  • 一天共有以下状态

    • 没有操作 （其实我们也可以不设置这个状态）

    • 第一次持有股票

    • 第一次不持有股票

    • 第二次持有股票

    • 第二次不持有股票

  • dp[i][j] 中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j] 表示第i天状态j所剩最大现金。

• 确定递推公式

  • 达到 dp[i][1] 状态，有两个具体操作：

    • 操作一：第i天买入股票了，那么 dp[i][1] = dp[i-1][0] - prices[i]

    • 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

  • dp[i][2] 也有两个操作：

    • 操作一：第i天卖出股票了，那么 dp[i][2] = dp[i - 1][1] + prices[i]

    • 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

  • 同理可推出剩下状态部分：

    • dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

    • dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

• dp数组如何初始化

  • 第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
  • 第0天做第一次买入的操作，dp[0][1] = -prices[0];
  • 第0天做第一次卖出的操作，初始值可以理解当天买入，当天卖出，dp[0][2] = 0
  • 第0天做第二次买入操作，初始化为：dp[0][3] = -prices[0] ;
  • 第0天做第二次卖出初始化 dp[0][4] = 0

• 遍历顺序

  • 从前向后遍历

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][]dp=new int[n][5];
        // 初始化
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[0][2]=0;
        dp[0][3]=-prices[0];
        dp[0][4]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=dp[i-1][0];
            // 第一次持有股票
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            // 第一次不持有股票
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            // 第二次持有股票
            dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            // 第二次不持有股票
            dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        return dp[n-1][4];
    }
}