746. 使用最小花费爬楼梯
题目
746. 使用最小花费爬楼梯 难度:easy
给你一个整数数组 cost
,其中 cost[i]
是从楼梯第 i
个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1:
输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。
示例 2:
输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。
提示:
2 <= cost.length <= 1000
0 <= cost[i] <= 999
方法一:动态规划
思路
根据题意,这题可以直接使用「动态规划」,在此之前的博文中,也有用到过「动态规划」算法;
要求使用最小的花费爬楼梯,即可理解为到达下标 n 所需要的花费;
创建 dp 数组用来表示最小花费,dp[i]
表示到达下标 i
的最小花费;
由于可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯,因此有 dp[0] = dp[1] = 0
;
当 2 ≤ i ≤ n 时,可以从下标 i − 1
使用 cost[i−1]
的花费达到下标 i,或者从下标 i − 2
使用 cost[i−2]
的花费达到下标 i。为了使总花费最小,dp[i] 应取上述两项的最小值,因此状态转移方程如下:
$$ dp[i] = min \{dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]\} $$
依次计算 dp 中的每一项的值,最终得到的 dp[n]
即为达到楼层顶部的最小花费。
下方代码中,py 的解法使用了滚动数组的思想进行了优化;
解题
Python:
这里使用了滚动数组的思想,来优化空间复杂度到 O(1)
;
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
prev = curr = 0
for i in range(2, n + 1):
nxt = min(curr + cost[i - 1], prev + cost[i - 2])
prev, curr = curr, nxt
return curr
Java:
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 0;
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];
}
}
62. 不同路径
题目
62. 不同路径 难度:medium
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入: m = 3, n = 7
输出: 28
示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3:
输入: m = 7, n = 3
输出: 28
示例 4:
输入: m = 3, n = 3
输出: 6
提示:
1 <= m, n <= 100
- 题目数据保证答案小于等于
2 * 10^9
方法一:动态规划
思路
根据题意,不难发现这题跟上一题有着异曲同工之妙,只是从一维变成了二维;
由于我们每一步只能从向下或者向右移动一步,因此要想走到 (i, j),如果向下走一步,那么会从 (i-1, j) 走过来;如果向右走一步,那么会从 (i, j-1) 走过来。因此,用 f(i, j) 表示从左上角走到 (i, j) 的路径数量,其中 i 和 j 的范围分别是 [0, m) 和 [0, n)。
可以写出动态规划转移方程:
$$ f(i,j) = f(i-1,j) + f(i,j-1) $$
同时需要设置一下边界条件,将所有的 f(0, j) 以及 f(i, 0) 都设置为1;
解题
Python:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
print(f)
for i in range(1, m):
for j in range(1, n):
f[i][j] = f[i - 1][j] + f[i][j - 1]
return f[m - 1][n - 1]
Java:
class Solution {
public int uniquePaths(int m, int n) {
int[][] f = new int[m][n];
for (int i = 0; i < m; ++i) {
f[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
f[0][j] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
}
方法二:数学
思路
从左上角到右下角的过程中,我们需要移动 m+n-2 次,其中有 m-1 次向下移动,n-1 次向右移动。因此路径的总数,就等于从 m+n-2 次移动中选择 m-1 次向下移动的方案数,即组合数:
$$ C_{m+n-2}^{m-1} = \tbinom{m+n-2}{m-1} = \frac{(m+n-2)!}{(m-1)!(n-1)!} $$
解题
Python:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return comb(m + n - 2, n - 1)
Java:
class Solution {
public int uniquePaths(int m, int n) {
long ans = 1;
for (int x = n, y = 1; y < m; ++x, ++y) {
ans = ans * x / y;
}
return (int) ans;
}
}
后记
📝 上篇精讲: 【算法题解】 Day11 数学
💖 我是 𝓼𝓲𝓭𝓲𝓸𝓽,期待你的关注;
👍 创作不易,请多多支持;
🔥 系列专栏: 算法题解