难度说明：🟢简单🟡中等🔴困难

动态规划

todo: 动态规划解题模板、思路、适用场景

动态规划解析步骤模板：

• 【步骤1】：确定dp数组及下标含义（根据穷举规律来理解分析）
• 【步骤2】：得到推导公式（结合规律得到dp[k]的推导公式，即dp[k]与前面的元素有什么联系）
• 【步骤3】：初始化dp数组（处理初始状态和一些临界的情况）
• 【步骤4】：确定循环（通过循环和推导公式填充dp数组）
• 【步骤5】：验证dp数组正确性

斐波那契数列

​ 斐波那契数列公式：f(0)=0、f(1)=1、f(2)=0+1=1、f(3)=1+1=2、f(4)=1+2=3

递归法实现

// 递归解法
public int fibonacci01(int n) {
    // 递归出口
    if (n == 0 || n == 1) {
        return n;
    }
    // 执行递归
    return fibonacci01(n - 1) + fibonacci01(n - 2);
}

动态规划实现

// 动态规划
public int[] fibonacci02(int n) {
    // 定义数组记录前面的结果
    int[] res = new int[n];
    // 初始化结果集
    res[0] = 0;
    res[1] = 1;
    for (int i = 2; i < n; i++) {
        res[i] = res[i - 1] + res[i - 2];
    }
    // 返回最终的结果(整个斐波那契数列，如果返回对应位置的数字则根据下标索引定位即可)
    return res;
}

🟢01-爬楼梯（70）

1.题目内容

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

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

示例 1：

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

示例 2：

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

2.题解思路

👻方法1：动态规划

​ 可以先通过穷举方法理解思路的演变，例如从n=0开始，依次分析爬n阶需要多少种方法：

• n=0：1种（0）
• n=1：1种（1）
• n=2：2种（1+1、0+2）
• n=3：3种（1+2 1+1+1、0+2+1）
• n=4：5种（1+1+2、0+2+2 1+2+1、1+1+1+1、0+2+1+1）
• 结合规律分析：当要爬第n阶的时候，它的方法相当于是基于第n-1阶的方案再爬1阶 + 基于第n-2的方案再爬2阶，即等价于爬N阶的方案个数实际等于爬N-1+爬N-2的方案个数，基于此可以看到这种思路很像斐波那契数列的调调，可以基于动态规划思路实现（将问题拆分为多个子问题）

public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    // 定义初始结果
    dp[0] = 1;
    dp[1] = 1;

    // 爬N阶的思路（f(n) = f(n-1) + f(n-2)）
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    // 返回爬n阶的方案(数组从0开始计数)
    return dp[n - 1];
}

• 复杂度分析

  • 时间复杂度：O(n)（遍历数组元素）

  • 空间复杂度：O(n)（定义了一个辅助数组来存储结果）

​ 也可以基于滚动数组的方案来优化上述思路

public int climbStairs2(int n) {
    // 定义指针
    int p = 1, q = 1, r = 2;
    if (n == 0) return p;
    if (n == 1) return q;
    if (n == 2) return r;
    for (int i = 3; i <= n; i++) {
        p = q;
        q = r;
        r = p + q;
    }
    // 返回爬n阶的方案(数组从0开始计数)
    return r;
}


// 简化写法：
public int climbStairs(int n) {
    // 定义指针
    int p = 0, q = 0, r = 1;

    // 爬N阶的思路（f(n) = f(n-1) + f(n-2)）
    for (int i = 1; i <= n; i++) {
        p = q;
        q = r;
        r = p + q;
    }
    // 返回爬n阶的方案(数组从0开始计数)
    return r;
}

🟢02-杨辉三角（118）

1.题目内容

​ 给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

2.题解思路

​ 核心：观察元素生成规律，对齐每一行结果集，每一行的元素首尾都为1，中间的元素为其对应位置的左上方+正上方的元素之和，基于此可以构建一个二维数组存储每一行的元素。然后依次遍历构建的二维数据封装返回的结果集

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
// 每一行的首尾元素均为1：c[i][0] = c[i][i] = 1
// 中间元素满足：c[i][j] = c[i-1][j-1] + c[i-1][j]

👻方法1：规律法（根据观察规律生成数组元素）

• 每一行的首尾元素均为1：c[i][0] = c[i][i] = 1
• 中间元素满足：c[i][j] = c[i-1][j-1] + c[i-1][j]

PS：上述形式是通过二维数组来进行表达，实际上结果要求List<List<Integer>>格式，一种思路是先借助二维数组封装元素便于理解，随后遍历二维数组；一种是直接使用List<List<Integer>>无序额外引入二维数组存储（本质都是基于二维数组访问的概念）

// 方式1：二维数组转化（类似动态规划思路）
public List<List<Integer>> generate(int numRows) {
    // 构建一个二维数组存储元素(n*n)
    int[][] arr = new int[numRows+1][numRows+1];
    arr[0][0] = 1; // 初始化第0行
    arr[1][0] = 1; // 初始化第1行
    arr[1][1] = 1;
    // 遍历二维数组依次存储数据
    for (int i = 2; i <= numRows; i++) {
        for (int j = 0; j <= numRows; j++) {
            // 首尾元素置为1，其他中间元素满足c[i][j]=c[i-1][j-1]+c[i-1][j]
            if(j==0 || i==j){
                // 首尾元素置为1
                arr[i][j] = 1;
            }else{
                // 其他元素满足当前元素=左上方+正上方的元素之和
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
            }
        }
    }
    // 遍历二维数组，返回封装结果
    List<List<Integer>> res = new ArrayList<>();
    for(int i=0;i<numRows;i++){
        List<Integer> temp = new ArrayList<>();
        for(int j=0;j<numRows;j++){
            // temp.add(arr[i][j]); // 需要去除掉默认的0元素
            if(arr[i][j]!=0){
                temp.add(arr[i][j]);
            }
        }
        res.add(temp);
    }
    // 返回结果集合
    return res;
}

// 方式2：直接遍历封装结果集
public List<List<Integer>> generate(int numRows) {
    // 构建一个二维数组(这个二维概念不一定要数组，也可以基于List<List<Integer>>构建)存储元素(n*n)
    List<List<Integer>> res = new ArrayList<>();

    // 存储数据
    for (int i = 0; i < numRows; i++) { // 外层循环
        // 初始化临时列表存储当前行生成的数据
        List<Integer> temp = new ArrayList<>();
        for (int j = 0; j <= i; j++) { // 内存循环：该行元素个数受限于当前行数
            // 首尾元素置为1，其他中间元素满足c[i][j]=c[i-1][j-1]+c[i-1][j]
            if(j==0 || i==j){
                // 首尾元素置为1（在该行追加元素）
                temp.add(1);
            }else{
                // 其他元素满足当前元素=左上方+正上方的元素之和
                temp.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
            }
        }
        // 将当前行加入结果集
        res.add(temp);
    }
    // 返回结果集合
    return res;
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟡03-打家劫舍（198）

1.题目内容

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

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

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

2.题解思路

👻方法1：动态规划

​ 先分析偷窃规律，然后分析出其规律方程（n表示多少间房屋，从n=1开始分析）

• n=1：只有一间房屋，则偷这一间即为最高
• n=2：有两间房屋，由于相邻两间不能连着偷，因此只能偷其中一间，选择价值较高的来头
• n=K：当n>2，则此时偷窃有两种思路（对于每一个房间都可以选择偷或者不偷）
  • 如果偷窃第K间房屋，则不能偷窃第K-1间房屋，偷窃总金额=max（前K-2间房屋金额）+第K间房屋金额
  • 如果不偷第K间房屋，则偷窃总金额=max（前K-1间房屋金额）
• 基于上述分析，则可得到相应的方程式：dp[k]=max(dp[k-2]+nums[k],dp[k-1])，也就是说最终偷窃的总金额是由这两种场景构成的
• 说明：代码实现上可以先把大致框架定下来（动态规划的设计），然后在调试的过程中去完善边界条件

public int rob(int[] nums) {
    // 定义数组存储每到一个房间可能偷到的最大金额
    int[] dp = new int[nums.length];

    // 边界值判断
    if(nums==null || nums.length==0){
        return 0;
    }
    if(nums.length==1){
        return nums[0];
    }

    // 初始化
    dp[0] = nums[0]; // 只有一间房屋
    dp[1] = Math.max(nums[0], nums[1]); // 有两间房屋，不能连着偷，选择最大值

    // 遍历房间，计算每个房间可能偷到的最大金额
    for(int k = 2; k < nums.length; k++) {
        // 当偷到第k间房，有两种方案（偷或者不偷，分别计算两种情况下可能偷到的金额，然后取最大值）
        int todo = dp[k-2] + nums[k]; // 偷了K，则不能偷K-1，其max为dp[K-2]+nums[i]
        int undo = dp[k-1]; // 不偷K，其max为dp[k-1]
        // 记录最大值（选择偷窃方案，然后进入下一步）
        dp[k] = Math.max(todo, undo);
    }
    // 返回偷窃的最大值
    return dp[nums.length-1];
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

​ 类似地，优化思路参考滚动数组概念存储结果，每间房的最高金额和前两间有关，因此可以使用滚动数组进行操作

public class Solution2 {
    public int rob(int[] nums) {
        // 边界值判断
        if(nums==null || nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }

        // 初始化（初始化p、q、r概念，分别表示k-2、k-1、k）
        int p = nums[0]; // 只有一间房屋(p初始化对应1间)
        int q = Math.max(nums[0], nums[1]); // 有两间房屋，不能连着偷，选择最大值（q初始化对应2间选一间）
        int max = Integer.MIN_VALUE; // 定义第K间房的最大偷窃金额
        // 遍历房间，计算每个房间可能偷到的最大金额
        for(int k = 2; k < nums.length; k++) {
            // 当偷到第k间房，有两种方案（偷或者不偷，分别计算两种情况下可能偷到的金额，然后取最大值）
            int todo = p + nums[k]; // 偷了K，则不能偷K-1，其max为dp[K-2]+nums[i]
            int undo = q; // 不偷K，其max为dp[k-1]
            // 记录最大值（选择偷窃方案，然后进入下一步）
            max = Math.max(todo, undo);
            // 数组滚动,进入下一轮
            p = q;
            q = max;
        }
        // 返回偷窃的最大值
        return max;
    }
}

🟡04-完全平方数（279）

1.题目内容

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

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

示例 1：

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

示例 2：

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

2.题解思路

​ 先依次分析规律，然后基于此来梳理动态规划思路

• n=0：0
• n=1：min(dp[0]+1) =>1
• n=2：min(dp[1]+1) =>2
• n=3：min(dp[2]+1) =>3
• n=4：min(dp[3]+1,dp[0]+1) =>1
• n=5：min(dp[4]+1,dp[1]+1) =>2

👻方法1：动态规划

​ 此处将其转化为背包问题进行处理，正整数n就是背包，完全平方数就是物品（物品可以重复使用），则此处题意可以转化为怎样用最少得的物品数凑满整个背包。因此此处结合动态规划步骤进行思路剖析：

• 【步骤1】：确定dp数组和下标的含义=》dp[k]和为k的完全平方数的最少数量为dp[k]

• 【步骤2】：推导公式 =》dp[k]由dp[k-i*i]+1推导得出，要选择最小的dp[k]，因此递推公式为dp[k]=min(dp[k-i*i]+1,dp[k])

  • 以k=12为例进行分析，理解当前数和上一个数的跨度问题。其上一个数可以是11、8、3
    • 11 + 1*1 = 12
    • 8 + 2*2 = 12
    • 3 + 3*3 = 12
    • 基于此可以看到，上一个数只要要加一个完全平方数才能得到 k ，因此得到推导公式dp[k] = dp[k-i*i]+1，但由于这个方案可能会有很多种，因此要选择个数最少的那个方案，进而递推公式演化为dp[k]=min(dp[k-i*i]+1,dp[k])，基于此也就解释了为什么需要双层循环来实现，主要是为了定位那个所谓的i值

• 【步骤3】：dp数组初始化 =》dp[0]=0(结合题意理解分析)，非0下标的递推公式为dp[k]=min(dp[k-i*i]+1,dp[k])（因为每次都选min，因此此处dp[k]初始化应设置为最大值避免在递推过程中被覆盖）

• 【步骤4】：确定遍历顺序，完全背包概念

  • 如果求组合数：外层for循环遍历物品，内层for遍历背包

    // 外层遍历物品（i为物品、j为背包）
    for (int i = 1; i * i <= n; i++) { // 物品个数受限于背包容量
        // 内层遍历背包
        for (int j = i * i; j <= n; j++) { // 背包容量受限于n
            dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
        }
    }
    

  • 如果求排列数：外层for遍历背包，内层for循环遍历物品

    // 外层背包，内层物品
    for (int i = 1; i <= n; i++) { // 背包容量受限于n
        for (int j = 1; j * j <= i; j++) { // 物品个数受限于当前背包容量
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    

• 【步骤5】：举例推导数组

public class Solution {
    // 转化为完全背包问题：n为背包，完全平方数即为物品（可重复使用），将题意转化为用最少的物品数量凑满背包
    public int numSquares(int n) {
        // 1.定义动态数组(dp[k]表示和为k的完全平方数的最少数量)
        int[] dp = new int[n + 1];

        // 2.推导公式dp[k] = min(dp[k-i*i]+1,dp[k])

        // 3.dp数组初始化
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE; // 其余数组元素初始化为最大值，避免递推过程中被min覆盖
        }

        // 4.确定遍历顺序（完全背包概念）
        /* 实现思路1：外层物品、内层背包
        // 外层遍历物品（i为物品、j为背包）
        for (int i = 1; i * i <= n; i++) { // 物品个数受限于背包容量
            // 内层遍历背包
            for (int j = i * i; j <= n; j++) { // 背包容量受限于n
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
         */

        // 实现思路2：外层背包，内层物品
        for (int i = 1; i <= n; i++) { // 背包容量受限于n
            for (int j = 1; j * j <= i; j++) { // 物品个数受限于当前背包容量
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        // 返回结果
        return dp[n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numSquares(12));
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟡05-零钱兑换（322）

1.题目内容

给你一个整数数组 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

2.题解思路

👻方法1：动态规划

​ 转化为背包问题： coins不同面值的硬币（对应物品重量，物品个数无限制），amount背包容量

• 【步骤1】敲定dp数组：dp[k]表示凑成k金额所需的最少硬币个数
• 【步骤2】确定递归公式：dp[k] 可以由dp[k-coins[i]]+1进行递推，由于这个组合可能会有很多个，因此需要在循环中获取到min最小值（dp[k]=min(dp[k-coins[i]]+1,dp[k])）
• 【步骤3】初始化dp数组
  • dp[0] = 0，其他数据用MAX填充（因为递推过程中需要获取最小值，因此初始化设定为MAX避免被无效覆盖）
• 【步骤4】敲定循环（填充dp数组）：外层背包内层物品 VS 外层物品内层背包
• 【步骤5】验证dp数组

PS：可以看到此处和上述完全平方数的实现思路类似

/**
 * 322.零钱兑换
 */
public class Solution {

    // 转化为相应的完全背包问题：amount为背包容量，coins为物品重量（不限定物品个数），求如何使用最少数量的物品装满背包
    public int coinChange(int[] coins, int amount) {
        // 1.敲定dp数组（dp[k]表示装满K容量的最小物品个数，即对应凑满amount的最小coins个数（PS：不是所有K都能凑））
        int[] dp = new int[amount + 1];

        // 2.确认递推公式 dp[k] = min(dp[k-coins[i]] + 1, dp[k])

        // 3.初始化dp,使用max填充其他元素（因为递推过程中求的是min）
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;  // dp[i] = Integer.MAX_VALUE;（只要设置一个比amount大即可，能确保凑不上）
            // 如果此处设定为Integer.MAX_VALUE，则下方和amount比较的时候会被转为负数导致结果错误，因此粗出设定为一个比amount大的数即可
        }

        // 4.确定循环（填充dp）
        // 外层背包容量、内层物品个数
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                // dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); // 需限定条件
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        // 结果返回（返回dp[k],但并不是每个k都能凑，因此如果）
        // return dp[amount];
        return dp[amount] > amount ? -1 : dp[amount]; // 此处根据测试用例返回结果，正常直接返回对应元素，此处如果凑不满则设为-1

        // 5.验证
    }
}

• 复杂度分析

  • 时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度

  • 空间复杂度：O(S)。数组 dp 需要开长度为总金额S的空间

🟡06-单词拆分（139）

1.题目内容

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

2.题解思路

👻方法1：动态规划

• 【步骤1】敲定dp数组：dp[k]表示0到 k 位置是否可以由wordDict组成（能否被拆分）
• 【步骤2】状态转移公式：dp[k]若为true，则dp[j]为true、且[j,i]组成的字符串也在字典列表中
• 【步骤3】初始化dp数组：dp[0]没有含义初始化设置为true，其余设置为false
• 【步骤4】确认循环：外层背包、内层物品
• 【步骤5】验证dp数组

/**
 * 139.单词拆分
 */
public class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
        // 1.确定dp数组(dp[k]表示0-k的位置可以被拆分)
        boolean[] dp = new boolean[s.length() + 1];

        // 2.状态转移方程（如果dp[k]可以被拆分，则dp[j]也可以被拆分，且从j+1到K的位置也能被拆分）

        // 3.初始化dp(dp[0]为true，其余元素设为false)
        Arrays.fill(dp, false);
        dp[0] = true;

        // 4.敲定循环（外层背包，内层物品）
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // 如果dp[k]可以被拆分，则dp[j]也可以被拆分，且从j+1到i的位置也能被拆分
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }

        // 返回结果
        return dp[s.length()];
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟡07-最长递增子序列（300）

1.题目内容

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

2.题解思路

👻方法1：动态规划

• 【步骤1】确定dp （dp[k] 表示截止到nums[k]（以nums[k]结尾的最大子序列长度））
• 【步骤2】确定状态转移方程
  • 遍历过程中如果始终有一个较大的数接在较小的数后面，则相应会形成一个更长的子序列
  • 只要nums[i]严格大于其之前的数，则可构成升序序列
• 【步骤3】初始化dp
  • dp[i] = 1 (确保每一个元素都是一个单独的升序子序列)
• 【步骤4】确定循环
  • 外层循环：遍历每个nums[i]元素，计算0-i 之间的最大子序列值
  • 内存循环：在0-i之间找比num[i]小的元素，看接在它后面的方案，选择最长的那种max(dp[i],dp[j]+1)
• 【步骤5】验证dp（以[10,9,2,5,3,7,101,18]为例进行分析）
  • i=0 10：10前面没有元素，因此其本身就是一个升序子序列，无需做任何操作（此时dp[0]默认初始化为1也不需要做任何操作，即dp[0]=1）
  • i=1 9：9前面没有比9小的数，因此无法构成一个更长的生序序列，因此dp[1]=1（默认就是1也不需要做任何操作）
  • i=2 2：类似的，2前面没有比2小的数，dp[2]=1
  • i=3 5：依次从0下标开始遍历到元素5所在下标位置，发现2<5，说明5可以接在2后面，那么dp[3]应该取较大值max(dp[i],dp[j]+1)，dp[3]初始为1，dp[j]+1 对应为dp[2]+1值为2，因此更新dp[3]为2。内层循环遍历到下标3结束了，因此最终dp[3]=2
  • i=4 3：类似的，在3前面的比3小的数只有2，因此对比接在2之后的方案取最大值：max(dp[4],dp[2]+1)(dp[4]默认为1) =》最终更新dp[4]=2
  • i=5 7：类似的，内层循环从0-5内进行遍历，看7可以接在哪个比他小的数后面
    • 内层循环 j=2 2<7 =》max(dp[5],dp[2]+1)（dp[5]初始化为1）=》max(1,2)因此dp[5] 被更新为2
    • 内层循环 j=3 5<7 =》max(dp[5],dp[3]+1)（dp[5]原为2）=》max(2,3)因此dp[5] 被更新为3
    • 内层循环 j=4 3<7 =》max(dp[5],dp[4]+1)（dp[5]原为3）=》max(3,3)因此dp[5] 还是为3
    • 内层循环结束，最终dp[5]=3
  • i=6 101：类似的，内存循环从0-6内进行遍历，看101可以接在哪个比他小的数后面
    • 内层循环 j=0 10<101 =》max(dp[6],dp[0]+1)（dp[6]初始化为1）=》max(1,2)因此dp[6] 被更新为2
    • 内层循环 j=1 9<101 =》max(dp[6],dp[1]+1)（dp[6]原为2）=》max(2,2)因此dp[6] 被更新为2
    • 内层循环 j=2 2<101 =》max(dp[6],dp[2]+1)（dp[6]原为2）=》max(2,2)因此dp[6] 被更新为2
    • 内层循环 j=3 5<101 =》max(dp[6],dp[3]+1)（dp[6]原为2）=》max(2,3)因此dp[6] 被更新为3
    • 内层循环 j=4 3<101 =》max(dp[6],dp[4]+1)（dp[6]原为3）=》max(3,3)因此dp[6] 被更新为3
    • 内层循环 j=5 7<101 =》max(dp[6],dp[5]+1)（dp[6]原为3）=》max(3,4)因此dp[6] 还是为4
    • 内层循环结束，最终dp[6]=4
  • i=7 18：类似的，内存循环从0-7内进行遍历，看18可以接在哪个比他小的数后面
    • 内层循环 j=0 10<18=》max(dp[7],dp[0]+1)（dp[7]初始化为1）=》max(1,2)因此dp[7] 被更新为2
    • 内层循环 j=1 9<18 =》max(dp[7],dp[1]+1)（dp[7]原为2）=》max(2,2)因此dp[7] 被更新为2
    • 内层循环 j=2 2<18 =》max(dp[7],dp[2]+1)（dp[7]原为2）=》max(2,2)因此dp[7] 被更新为2
    • 内层循环 j=3 5<18 =》max(dp[7],dp[3]+1)（dp[7]原为2）=》max(2,3)因此dp[7] 被更新为3
    • 内层循环 j=4 3<18 =》max(dp[7],dp[4]+1)（dp[7]原为3）=》max(3,3)因此dp[7] 被更新为3
    • 内层循环 j=5 7<18 =》max(dp[7],dp[5]+1)（dp[7]原为3）=》max(3,4)因此dp[7] 还是为4
    • 内层循环 j=6 101<18 不成立 舍弃这个
    • 内层循环结束，最终dp[7]=4
  • 外层循环结束，此时得到dp数组为记录了以nums[i]元素结尾的最长子序列的长度，如果要得到整个数组的最长子序列，则还需再次对dp数组进行遍历，得到dp数组元素的最大值

/**
 * 300.最长子序列
 */
public class Solution {

    public int lengthOfLIS(int[] nums) {
        // 1.确定dp（dp[i]表示以nums[i]元素结尾的最长子序列长度）
        int[] dp = new int[nums.length];

        // 2.敲定状态转移方程（以nums[i]结尾的序列，对于升序序列而言如果后面的元素大于前面的元素，则表示升序）

        // 3.初始化dp
        Arrays.fill(dp, 1); // dp元素初始化为1

        // 循环（因此校验以nums[i]结尾的元素的最长子序列）
        for (int i = 0; i < nums.length; i++) {
            // 内层循环（0-i中判断以nums[i]结尾的最长子序列）
            for (int j = 0; j < i; j++) {
                // 如果后一个元素大于前一个元素则为升序
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 则选择看接在0-i之间的哪个元素后面能构成更大的升序元素，计算其最大子序列长度即可
                }
            }
        }

        // 4.返回整个数组的最长子序列长度（dp[k]存储的是以某个元素结尾的最长子序列长度，因此此处需要遍历整个dp返回最大值）
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟡08-乘积最大子数组（152）

1.题目内容

​ 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

​ 测试用例的答案是一个 32-位 整数

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

2.题解思路

👻方法1：动态规划

• 【步骤1】dp数组：dp[k] 表示以nums[k]元素结尾的子数组的最大乘积
  • 此处考虑到元素可能为负的情况，相应需要维护一个数组用于表示以nums[k]元素结尾的子数组的最小乘积
  • dpMax(以nums[k]元素结尾的子数组的最大乘积) dpMin(以nums[k]元素结尾的子数组的最小乘积)
• 【步骤2】递推公式：涉及乘积需要讨论负数的情况（如果负数乘以一个很小的数可能会变成比较大的数，如果正数乘以负数则可能会变成负数）
  • 如何计算dpMax[i] ？
    • 如果nums[i] >= 0 正数要乘以大数才会更大
      • dpMax[i-1] > 0，此处dpMax[i] = dpMax[i-1] * nums[i]
      • dpMax[i-1] < 0，则如果直接累乘就会变成负数，此处dpMax[i] = nums[i]
    • 如果nums[i]<0 负数要乘以小数才会更大
      • dpMin[i-1] >= 0，此处dpMax[i] = nums[i]
      • dpMin[i-1] < 0，则如果直接累乘负负得正，此处dpMax[i] = dpMin[i-1] * nums[i]
    • 基于此可以分析dpMax[i]实际就是在三种情况中取最大max(dpMax[i-1] * nums[i],nums[i],dpMin[i-1] * nums[i])
  • 如何计算dpMin[i] ？
    • 如果nums[i] >= 0 正数要乘以小数才会更小
      • dpMin[i-1] > 0，此处直接累乘就会更大，所以选择dpMin[i] = nums[i]
      • dpMin[i-1] < 0，此处dpMin[i] = dpMin[i-1] * nums[i]
    • 如果nums[i]<0 负数要乘以大数才会更小
      • dpMax[i-1] >= 0，此处直接累乘会得到一个更大的负数dpMin[i] = dpMax[i-1] * nums[i]
      • dpMax[i-1] < 0，如果直接累乘负负得正，因此此处选择dpMin[i] = nums[i]
    • 基于此可以分析dpMin[i]实际就是在三种情况中取最小max(nums[i],dpMin[i-1] * nums[i],dpMax[i-1] * nums[i])
  • 综合分析，这两种情况都可以进行整合，不管是dpMax[i] 还是dpMin[i] 都是从那三个数当中取到最大值、最小值，这点是根据推演得到的
• 【步骤3】初始化dp
  • 此处初始化dpMax、dpMin
• 【步骤4】循环确认
  • 循环遍历nums元素，填充dp数组元素
• 【步骤5】验证dp

/**
 * 152.乘积最大子数组
 */
public class Solution {

    public int maxProduct(int[] nums) {
        // 1.定义dp（dp[k]表示以nums[k]结尾的子数组的最大乘积）
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];

        // 2.状态转化方程（区分nums[i]为正数、负数的情况）

        // 3.初始化dp数组
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int max = nums[0]; // 记录最大值（在遍历过程中记录，不需要额外遍历dp数组） int max = Integer.MIN_VALUE;

        // 4.循环遍历nums数组元素，计算累乘的最大值
        for (int i = 1; i < nums.length; i++) {
            // 记录最大乘积和最小乘积 (数据的乘积都是从dpMax[i-1]*nums[i]、nums[i]、dpMin[i-1]*nums[i] 这三种情况分析，因此不需单独拆分)
            dpMax[i] = Math.max(dpMax[i - 1] * nums[i], Math.max(nums[i], dpMin[i - 1] * nums[i]));
            dpMin[i] = Math.min(dpMax[i - 1] * nums[i], Math.min(nums[i], dpMin[i - 1] * nums[i]));
            // 遍历过程中更新max
            max = Math.max(max, dpMax[i]);
        }
        return max;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟡09-分割等和子集（416）

1.题目内容

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

示例 1：

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

示例 2：

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

2.题解思路

👻方法1：动态规划

复杂度分析

• 时间复杂度：
• 空间复杂度：

🟡10-最长有效括号（123）

1.题目内容

2.题解思路

👻方法1：

复杂度分析

• 时间复杂度：
• 空间复杂度：