当前位置：首页 > article >正文

LeetCode刷题日记之动态规划（一）

article 2024/10/27 18:29:49

前言

在结束了贪心算法的第一轮学习后，博主将开启动态规划的探索之旅。这篇文章将分享几道经典的动态规划题目，帮助大家逐步理解这种更复杂但非常高效的解题方法✍✍✍

爬楼梯

LeetCode题目链接

就是爬n阶楼梯，每次可以爬1或者2个台阶，有多少种方法可以爬上去呢？

请添加图片描述

我们来梳理思路

这道题可以使用动态规划来解决，到达第 n 阶的总方法数等于到达第 n-1 阶的方法数与到达第 n-2 阶的方法数之和，为什么这么说呢🤔🤔🤔因为达第 n 阶的方式可以通过从第 n-1 阶爬 1 个台阶到达第 n 阶与从第n-2 阶爬 2 个台阶到达第 n 阶这两种情况累加得出。所以可以构建一个动态规划数组 dp，其中 dp[i] 表示到达第 i 阶的方法数🐶🐶🐶

紧接着来梳理动态规划的五部曲

确定dp数组和下标含义
- 用数组dp[i]表示到达第i阶的方法总数
确定递推公式
- 要到达第 i 阶，我们可以从第 i-1 阶爬一个台阶，或者从第 i-2 阶爬两个台阶。所以递推公式为dp[i]=dp[i-1]+dp[i-2]
dp数组如何初始化
- dp[1] = 1，表示只有 1 种方法到达第 1 阶（爬 1 个台阶）。 dp[2] = 2，表示有 2 种方法到达第 2 阶（分别是爬 1 个台阶两次，或者爬 2 个台阶一次）。
确定遍历顺序
- 从第3阶开始到第n阶
举例推导dp数组

dp[1] = 1
dp[2] = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8

完整代码如下

class Solution {
    public int climbStairs(int n) {
        if(n == 1) return 1; //特殊情况，如果只有一阶楼梯，返回1
        int[] dp = new int[n + 1];//定义dp数组
        
        //初始化dp数组
        dp[1] = 1;
        dp[2] = 2;

        //遍历楼梯阶数
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];//递归公式
        }

        return dp[n];
    }
}

杨辉三角

LeetCode题目链接

这道题就是给一个非负整数numRows，然后要生成杨辉三角的前numRows行

请添加图片描述

我们来思路梳理

杨辉三角是一个二维数组，其中每一行的元素是通过上一行相邻两个元素相加得到的。生成前 numRows 行的杨辉三角，可以用动态规划的思想构建，每一行的第一个和最后一个元素都是 1，其他元素则是它上面一行相邻两个元素之和🤔🤔🤔

我们接着来梳理动态规划的五部曲

确定dp数组和下标含义
- 我们用一个二维数组 triangle 来存储杨辉三角的每一行，triangle[i][j] 表示杨辉三角第 i 行的第 j 个元素
确定递推公式
- 每一行的第一个和最后一个元素都是 1
- 对于其他元素，我们根据上一行相邻两个元素之和来推导：triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
dp数组初始化
- 第 1 行是 [1]，第 2 行是 [1, 1]
- 从第 3 行开始，需要根据递推公式填充中间的元素
确定遍历顺利
- 外层循环从第 3 行开始遍历到第 numRows 行
- 内层循环遍历每行的元素，从第 2 个到倒数第 2 个元素，依次填充当前行
举例推导dp数组

numRows = 5
第 1 行：[1]
第 2 行：[1, 1]
第 3 行：[1, 2, 1]
第 4 行：[1, 3, 3, 1]
第 5 行：[1, 4, 6, 4, 1]

完整代码如下

class Solution {
    public List<List<Integer>> generate(int numRows) {
        //初始化列表来存储杨辉三角的所有行
        List<List<Integer>> triangle = new ArrayList();

        if(numRows == 0){
            return triangle;
        }

        //第一行固定为1
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);
        
        //从第二行开始递推
        for(int i = 1; i < numRows; i++){
            List<Integer> row = new ArrayList<>();//创建当前行
            List<Integer> prevRow = triangle.get(i - 1);//提取前一行
            row.add(1);//行首数字为1
            for(int j = 1; j < i; j++){
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }
            row.add(1);//行尾数字为1
            triangle.add(row);
        }
        return triangle;
    }
}

打家劫舍

LeetCode题目链接

这道题是一个数组，数组中的元素nums[i]代表的意思是i号房屋藏匿了nums[i]数量的现金，作为小偷，不能偷窃相邻房屋的现金，不然会触发报警装置，你最高能偷取的现金是多少

请添加图片描述

我们来梳理思路

这道题的核心思路在于对于每一间房屋有两种选择：1.不偷则能够获得的最大金额就是从前面屋子偷得的最大金额 2.偷的话能获得的最大金额就是当前房间的钱加上从两间房子前偷的最大金额

我们来接着梳理动态规划的五步曲

确定dp数组和下标含义
- 用dp[i]表示偷到第i间房时能够获得的最大金额
确定递推公式
- dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i])这表示要么不偷当前房屋，延续前一间房的最大金额，要么偷当前房屋，加上前两间房的金额
dp数组如何初始化

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

确定遍历顺序
- 从第三间房（即 i = 2）开始，依次计算每一间房的最大金额，直到最后一间房
举例推导dp数组

nums = [2, 7, 9, 3, 1]
dp[0] = 2（只能偷第一间房）
dp[1] = max(2, 7) = 7（选择偷第二间房）
dp[2] = max(7, 2 + 9) = 11（选择偷第 1 和第 3 间房）
dp[3] = max(11, 7 + 3) = 11（选择偷第 1 和第 3 间房）
dp[4] = max(11, 11 + 1) = 12（选择偷第 1、3 和第 5 间房）

完整代码如下

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;//如果没房子
        if(nums.length == 1) return nums[0];//如果只有一间房

        //定义并初始化dp数组
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        //从第三间房间开始遍历
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[nums.length - 1];
    }
}