假设你正在爬楼梯。需要 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 阶

解题思路

这个问题是一个经典的动态规划问题，可以通过动态规划的方法来解决。思路如下：

定义状态：定义dp[i]表示到达第i阶楼梯有dp[i]种方法。
状态转移方程：到达第i阶楼梯可以从第i-1阶上来，也可以从第i-2阶上来。因此，dp[i] = dp[i-1] + dp[i-2]。
初始化：dp[0]=1（没有楼梯时我们认为有一种方法），dp[1]=1（只有一阶楼梯时只有一种方法）。
计算顺序：从第2阶楼梯开始计算直到第n阶。

完整代码

Python


class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Java


public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

解题思路

要使用动态规划解决这个问题，我们可以定义一个状态数组dp，其中dp[i]表示能否到达数组中的第i个位置。动态规划的过程是从前向后逐步构建dp数组的值，直到最后一个元素。

具体步骤如下：

初始化：创建长度为nums.length的布尔数组dp，初始全部设为false。dp[0] = true，因为起始位置总是可达的。
状态转移：对于每一个位置i（i从1开始到nums.length - 1），遍历i之前的所有位置j（j从0到i-1），如果位置j是可达的（即dp[j] == true）并且从位置j跳跃的最大长度（nums[j]）加上j的位置能够达到或超过i（即j + nums[j] >= i），那么位置i也是可达的，设置dp[i] = true。
返回值：最后，返回dp数组的最后一个值，即dp[nums.length - 1]，表示是否能够到达最后一个下标。

完整代码

Python


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [False] * len(nums)
        dp[0] = True  # 起始位置总是可达的
        for i in range(1, len(nums)):
            for j in range(i):
                # 如果j是可达的，并且从j可以跳到i或更远，则将i标记为可达
                if dp[j] and j + nums[j] >= i:
                    dp[i] = True
                    break  # 找到一个可达的j就足够了，无需继续查找
        return dp[-1]  # 返回是否可以到达最后一个位置

代码优化

这个动态规划解法可通过142个测试用例，有的会因为时间过长失败，可以通过优化来减少其时间复杂度。原始的解法中，我们使用了嵌套循环，导致时间复杂度为O(n^2)。优化的思路是利用贪心算法的原理来更新一个变量，记录当前能够到达的最远距离，这样可以避免内层的循环，将时间复杂度降低到O(n)。


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxReach = 0  # 初始化最远可到达位置
        for i, jump in enumerate(nums):
            if i > maxReach:  # 如果当前位置i超出了之前可达的最远距离maxReach，则无法到达i
                return False
            maxReach = max(maxReach, i + jump)  # 更新可到达的最远位置
            if maxReach >= len(nums) - 1:  # 如果maxReach已经到达或超过最后一个位置，则可以到达
                return True
        return False  # 如果遍历结束还没有返回True，则表示不能到达最后一个位置

Java


public class Solution {
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true; // 初始化起点为可达
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // 如果j是可达的，并且从j可以跳到i或更远，则将i标记为可达
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break; // 找到一个可达的j就足够了，无需继续查找
                }
            }
        }
        return dp[nums.length - 1]; // 返回是否可以到达最后一个位置
    }
}

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

解题思路

对于“最小路径和”这个问题，我们同样可以使用动态规划的方法来解决。这个问题的目标是找到从左上角到右下角的路径，使得路径上的数字总和为最小。

解题思路如下：

定义状态：dp[i][j]表示从左上角到达点(i, j)的最小路径和。
状态转移方程：到达点(i, j)的路径可以从上方(i-1, j)或左方(i, j-1)来，因此dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。需要特别注意边界条件，即当i或j为0时，只有一条路径可走。
初始化：dp[0][0] = grid[0][0]，即起点的最小路径和就是其自身的值。对于第一行和第一列的其他元素，因为它们只能从一个方向来（要么是上边，要么是左边），所以可以直接累加。
计算顺序：从左上角开始，逐行或逐列填充dp数组，直到右下角。
返回值：dp数组右下角的值，即dp[m-1][n-1]，代表了从左上角到右下角的最小路径和。

完整代码

Python


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
            
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
                
        return dp[-1][-1]

Java


public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        
        return dp[m-1][n-1];
    }
}

118. 杨辉三角

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

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

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

1 <= numRows <= 30

解题思路

生成杨辉三角的过程可以通过动态规划的方法来实现。每一行的数字是基于上一行的数字计算得来的，具体规则是：每一行的第一个和最后一个数字都是1，对于其中的其他数字，即第i行的第j个数字（行列均从0开始计数），可以通过上一行的第j-1个数字和第j个数字之和获得，即triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]。

解题思路如下：

初始化：初始化一个列表triangle来存储整个杨辉三角。
外层循环：从第0行遍历到第numRows-1行。
- 每一行初始化一个列表row，首个元素设为1（因为每行的开始都是1）。
内层循环：从第1个元素遍历到当前行的倒数第二个元素（因为每行的最后一个元素也是1，已经确定）。
- 根据triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]的规则计算当前位置的元素，并添加到当前行列表row中。
行尾处理：在每一行的最后添加1（每行的结束都是1）。
将当前行添加到杨辉三角中：将构建好的当前行row添加到triangle中。
返回结果：返回triangle。

完整代码

Python


class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle = []
        
        for i in range(numRows):
            row = [None for _ in range(i + 1)]  # 初始化当前行
            row[0], row[-1] = 1, 1  # 每行的开始和结束都是1
            
            for j in range(1, len(row) - 1):  # 计算中间的值
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]
                
            triangle.append(row)  # 将当前行添加到杨辉三角中
        
        return triangle

Java


public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();
        
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {  // 每行的开始和结束都是1
                    row.add(1);
                } else {
                    row.add(triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j));  // 计算中间的值
                }
            }
            
            triangle.add(row);  // 将当前行添加到杨辉三角中
        }
        
        return triangle;
    }
}

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

解题思路

接雨水问题可以通过动态规划来解决。核心思想是计算每个柱子上方能接多少雨水，这取决于该柱子左右两侧最高柱子的高度。具体来说，某个位置能接的雨水量，等于该位置左侧最高柱子和右侧最高柱子中较矮的一个的高度减去当前柱子的高度。

动态规划的步骤如下：

计算每个位置的左侧最大高度：遍历一次高度数组height，计算每个位置左侧的最大高度，存储在数组leftMax中。
计算每个位置的右侧最大高度：再次遍历高度数组height，但这次是从右向左遍历，计算每个位置右侧的最大高度，存储在数组rightMax中。
计算每个位置上方能接的雨水量：遍历每个位置，使用min(leftMax[i], rightMax[i]) - height[i]来计算每个位置上方能接的雨水量。如果这个值是负数，则说明在该位置不会积水，因此将其视为0。
求和：将每个位置上方能接的雨水量相加，得到总的接雨水量。

完整代码

Python


class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
 
        n = len(height)
        leftMax = [0] * n
        rightMax = [0] * n
        water = 0
 
        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i-1], height[i])
        
        rightMax[n-1] = height[n-1]
        for i in range(n-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], height[i])
        
        for i in range(n):
            water += min(leftMax[i], rightMax[i]) - height[i]
        
        return water

Java


public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
 
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        int water = 0;
 
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
 
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }
 
        for (int i = 0; i < n; i++) {
            water += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
 
        return water;
    }
}

------------------------------

总结不易。看到这了，觉得有用的话点个赞吧。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/709776

力扣大厂热门面试算法题 - 动态规划_大厂面试热门题目 算法

70. 爬楼梯

解题思路

完整代码

Python

Java

55. 跳跃游戏

解题思路

完整代码

Python

代码优化

Java

64. 最小路径和

解题思路

完整代码

Python

Java

118. 杨辉三角

解题思路

完整代码

Python

Java

42. 接雨水

解题思路

完整代码

Python

Java

力扣大厂热门面试算法题 - 动态规划_大厂面试热门题目算法