数据结构精品课 已更新到 V2.1, 手把手刷二叉树系列课程 上线。
LeetCode | 力扣 | 难度 |
---|---|---|
45. Jump Game II | 45. 跳跃游戏 II | 🟠 |
55. Jump Game | 55. 跳跃游戏 | 🟠 |
———–
经常有读者在后台问,动态规划和贪心算法到底有啥关系。我们之前的文章 贪心算法之区间调度问题 就说过一个常见的时间区间调度的贪心算法问题。
说白了,贪心算法可以理解为一种特殊的动态规划问题,拥有一些更特殊的性质,可以进一步降低动态规划算法的时间复杂度。那么这篇文章,就讲 LeetCode 上两道经典的贪心算法:跳跃游戏 I 和跳跃游戏 II。
我们可以对这两道题分别使用动态规划算法和贪心算法进行求解,通过实践,你就能更深刻地理解贪心和动规的区别和联系了。
这是力扣第 55 题「 跳跃游戏」,难度是中等,但实际上比较简单,看题目:
不知道读者有没有发现,有关动态规划的问题,大多是让你求最值的,比如最长子序列,最小编辑距离,最长公共子串等等等。这就是规律,因为动态规划本身就是运筹学里的一种求最值的算法。
那么贪心算法作为特殊的动态规划也是一样,也一定是让你求个最值。这道题表面上不是求最值,但是可以改一改:
请问通过题目中的跳跃规则,最多能跳多远?如果能够越过最后一格,返回 true,否则返回 false。
所以说,这道题肯定可以用动态规划求解的。但是由于它比较简单,下一道题再用动态规划和贪心思路进行对比,现在直接上贪心的思路:
boolean canJump(int[] nums) {
int n = nums.length;
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
// 不断计算能跳到的最远距离
farthest = Math.max(farthest, i + nums[i]);
// 可能碰到了 0,卡住跳不动了
if (farthest <= i) {
return false;
}
}
return farthest >= n - 1;
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
bool canJump(vector<int>& nums) {
int n = nums.size();
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
// 不断计算能跳到的最远距离
farthest = max(farthest, i + nums[i]);
// 可能碰到了 0,卡住跳不动了
if (farthest <= i) {
return false;
}
}
return farthest >= n - 1;
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
def canJump(nums: List[int]) -> bool:
n = len(nums)
farthest = 0
for i in range(n - 1):
# 不断计算能跳到的最远距离
farthest = max(farthest, i + nums[i])
# 可能碰到了 0,卡住跳不动了
if farthest <= i:
return False
return farthest >= n - 1
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
func canJump(nums []int) bool {
n := len(nums)
farthest := 0
for i := 0; i < n-1; i++ {
// 不断计算能跳到的最远距离
farthest = max(farthest, i+nums[i])
// 可能碰到了 0,卡住跳不动了
if farthest <= i {
return false
}
}
return farthest >= n-1
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var canJump = function(nums) {
var n = nums.length;
var farthest = 0;
for (var i = 0; i < n - 1; i++) {
// 不断计算能跳到的最远距离
farthest = Math.max(farthest, i + nums[i]);
// 可能碰到了 0,卡住跳不动了
if (farthest <= i) {
return false;
}
}
return farthest >= n - 1;
};
你别说,如果之前没有做过类似的题目,还真不一定能够想出来这个解法。每一步都计算一下从当前位置最远能够跳到哪里,然后和一个全局最优的最远位置 farthest
做对比,通过每一步的最优解,更新全局最优解,这就是贪心。
很简单是吧?记住这一题的思路,看第二题,你就发现事情没有这么简单。。。
这是力扣第 45 题「 跳跃游戏 II」,也是让你在数组上跳,不过难度是 Hard,解法可没上一题那么简单直接:
现在的问题是,保证你一定可以跳到最后一格,请问你最少要跳多少次,才能跳过去。
我们先来说说动态规划的思路,采用自顶向下的递归动态规划,可以这样定义一个 dp
函数:
// 定义:从索引 p 跳到最后一格,至少需要 dp(nums, p) 步
int dp(int[] nums, int p);
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
// 定义:从索引 p 跳到最后一格,至少需要 dp(nums, p) 步
int dp(int nums[], int p);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
from typing import List
# 定义:从索引 p 跳到最后一格,至少需要 dp(nums, p) 步
def dp(nums: List[int], p: int) -> int:
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
// 定义:从索引 p 跳到最后一格,至少需要 dp(nums, p) 步
func dp(nums []int, p int) int {
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
// 定义:从索引 p 跳到最后一格,至少需要 dp(nums, p) 步
var dp = function(nums, p) {};
我们想求的结果就是 dp(nums, 0)
,base case 就是当 p
超过最后一格时,不需要跳跃:
if (p >= nums.length - 1) {
return 0;
}
根据前文
动态规划套路详解 的动规框架,就可以暴力穷举所有可能的跳法,通过备忘录 memo
消除重叠子问题,取其中的最小值最为最终答案:
class Solution {
int[] memo;
// 主函数
public int jump(int[] nums) {
int n = nums.length;
// 备忘录都初始化为 n,相当于 INT_MAX
// 因为从 0 跳到 n - 1 最多 n - 1 步
memo = new int[n];
Arrays.fill(memo, n);
return dp(nums, 0);
}
// 定义:从索引 p 跳到最后一格,至少需要 dp(nums, p) 步
int dp(int[] nums, int p) {
int n = nums.length;
// base case
if (p >= n - 1) {
return 0;
}
// 子问题已经计算过
if (memo[p] != n) {
return memo[p];
}
int steps = nums[p];
// 你可以选择跳 1 步,2 步...
for (int i = 1; i <= steps; i++) {
// 穷举每一个选择
// 计算每一个子问题的结果
int subProblem = dp(nums, p + i);
// 取其中最小的作为最终结果
memo[p] = Math.min(memo[p], subProblem + 1);
}
return memo[p];
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class Solution {
public:
vector<int> memo;
// 主函数
int jump(vector<int>& nums) {
int n = nums.size();
// 备忘录都初始化为 n,相当于 INT_MAX
// 因为从 0 跳到 n - 1 最多 n - 1 步
memo = vector<int>(n, n);
return dp(nums, 0);
}
// 定义:从索引 p 跳到最后一格,至少需要 dp(nums, p) 步
int dp(vector<int>& nums, int p) {
int n = nums.size();
// base case
if (p >= n - 1) {
return 0;
}
// 子问题已经计算过
if (memo[p] != n) {
return memo[p];
}
int steps = nums[p];
// 你可以选择跳 1 步,2 步...
for (int i = 1; i <= steps; i++) {
// 穷举每一个选择
// 计算每一个子问题的结果
int subProblem = dp(nums, p + i);
// 取其中最小的作为最终结果
memo[p] = min(memo[p], subProblem + 1);
}
return memo[p];
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class Solution:
memo = []
def jump(self, nums: List[int]) -> int:
n = len(nums)
self.memo = [n] * n
return self.dp(nums, 0)
def dp(self, nums: List[int], p: int) -> int:
n = len(nums)
# base case
if p >= n - 1:
return 0
# 子问题已经计算过
if self.memo[p] != n:
return self.memo[p]
steps = nums[p]
# 你可以选择跳 1 步,2 步...
for i in range(1, steps+1):
# 穷举每一个选择
# 计算每一个子问题的结果
subproblem = self.dp(nums, p+i)
# 取其中最小的作为最终结果
self.memo[p] = min(self.memo[p], subproblem+1)
return self.memo[p]
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
func jump(nums []int) int {
memo := make([]int, len(nums))
for i := range memo {
memo[i] = len(nums)
}
return dp(nums, 0, memo)
}
func dp(nums []int, p int, memo []int) int {
n := len(nums)
// base case
if p >= n-1 {
return 0
}
// 子问题已经计算过
if memo[p] != len(nums) {
return memo[p]
}
steps := nums[p]
// 你可以选择跳 1 步,2 步...
for i := 1; i <= steps && p+i < n; i++ {
// 穷举每一个选择
// 计算每一个子问题的结果
subproblem := dp(nums, p+i, memo)
// 取其中最小的作为最终结果
memo[p] = min(memo[p], subproblem+1)
}
return memo[p]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var jump = function(nums) {
// 备忘录都初始化为 nums.length,相当于 INT_MAX
// 因为从 0 跳到 n - 1 最多 n - 1 步
let n = nums.length;
let memo = new Array(n).fill(n);
return dp(nums, 0, memo);
}
function dp(nums, p, memo) {
let n = nums.length;
// base case
if (p >= n-1) {
return 0;
}
// 子问题已经计算过
if (memo[p] != n) {
return memo[p];
}
let steps = nums[p];
// 你可以选择跳 1 步,2 步...
for (let i=1; i<=steps; i++) {
// 穷举每一个选择
// 计算每一个子问题的结果
let subProblem = dp(nums, p+i, memo);
// 取其中最小的作为最终结果
memo[p] = Math.min(memo[p], subProblem + 1);
}
return memo[p];
}
这个动态规划应该很明显了,按照前文
动态规划套路详解 所说的套路,状态就是当前所站立的索引 p
,选择就是可以跳出的步数。
该算法的时间复杂度是 递归深度 × 每次递归需要的时间复杂度,即 O(N^2),在 LeetCode 上是无法通过所有用例的,会超时。
贪心算法比动态规划多了一个性质:贪心选择性质。我知道大家都不喜欢看严谨但枯燥的数学形式定义,那么我们就来直观地看一看什么样的问题满足贪心选择性质。
刚才的动态规划思路,不是要穷举所有子问题,然后取其中最小的作为结果吗?核心的代码框架是这样:
int steps = nums[p];
// 你可以选择跳 1 步,2 步...
for (int i = 1; i <= steps; i++) {
// 计算每一个子问题的结果
int subProblem = dp(nums, p + i);
res = min(subProblem + 1, res);
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
int steps = nums[p];
// 你可以选择跳 1 步,2 步...
for (int i = 1; i <= steps; i++) {
// 计算每一个子问题的结果
int subProblem = dp(nums, p + i);
res = min(subProblem + 1, res);
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
steps = nums[p]
# 你可以选择跳 1 步,2 步...
for i in range(1, steps+1):
# 计算每一个子问题的结果
sub_problem = dp(nums, p + i)
res = min(sub_problem + 1, res)
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
steps := nums[p]
// 你可以选择跳 1 步,2 步...
for i := 1; i <= steps; i++ {
// 计算每一个子问题的结果
subProblem := dp(nums, p+i)
res = min(subProblem+1, res)
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
// 选择一个元素开始跳跃
var jump = function(nums) {
// 数组长度
var n = nums.length;
// dp函数用于计算到达数组末尾的最小跳跃数
var dp = function(nums, p) {
// 如果已经到达数组末尾
if (p == n - 1) {
return 0;
}
// 定义一个变量表示必须跳的最小步数
var res = Number.MAX_VALUE;
// 计算当前位置能跳的步数
var steps = nums[p];
// 遍历当前位置能跳的所有步数
for (var i = 1; i <= steps; i++) {
// 计算每一个子问题的结果
var subProblem = dp(nums, p + i);
// 选择步数最小的子问题并加1
res = Math.min(subProblem + 1, res);
}
return res;
};
// 从第一个元素开始跳跃
return dp(nums, 0);
};
for 循环中会陷入递归计算子问题,这是动态规划时间复杂度高的根本原因。
但是,真的需要「递归地」计算出每一个子问题的结果,然后求最值吗?直观地想一想,似乎不需要递归,只需要判断哪一个选择最具有「潜力」即可:
比如上图这种情况,我们站在索引 0 的位置,可以向前跳 1,2 或 3 步,你说应该选择跳多少呢?
显然应该跳 2 步调到索引 2,因为 nums[2]
的可跳跃区域涵盖了索引区间 [3..6]
,比其他的都大。如果想求最少的跳跃次数,那么往索引 2 跳必然是最优的选择。
你看,这就是贪心选择性质,我们不需要「递归地」计算出所有选择的具体结果然后比较求最值,而只需要做出那个最有「潜力」,看起来最优的选择即可。
绕过这个弯儿来,就可以写代码了:
int jump(int[] nums) {
int n = nums.length;
int end = 0, farthest = 0;
int jumps = 0;
for (int i = 0; i < n - 1; i++) {
farthest = Math.max(nums[i] + i, farthest);
if (end == i) {
jumps++;
end = farthest;
}
}
return jumps;
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
int jump(vector<int>& nums) {
int n = nums.size();
int end = 0, farthest = 0;
int jumps = 0;
for (int i = 0; i < n - 1; i++) {
farthest = max(nums[i] + i, farthest);
if (end == i) {
jumps++;
end = farthest;
}
}
return jumps;
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
def jump(nums: List[int]) -> int:
n = len(nums)
end, farthest, jumps = 0, 0, 0
for i in range(n - 1):
farthest = max(nums[i] + i, farthest)
if end == i:
jumps += 1
end = farthest
return jumps
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
func jump(nums []int) int {
n := len(nums)
end, farthest, jumps := 0, 0, 0
for i := 0; i < n-1; i++ {
farthest = max(farthest, nums[i]+i)
if end == i {
jumps++
end = farthest
}
}
return jumps
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var jump = function(nums) {
var n = nums.length;
var end = 0, farthest = 0;
var jumps = 0;
for (var i = 0; i < n - 1; i++) {
farthest = Math.max(nums[i] + i, farthest);
if (end == i) {
jumps++;
end = farthest;
}
}
return jumps;
};
结合刚才那个图,就知道这段短小精悍的代码在干什么了:
i
和 end
标记了可以选择的跳跃步数,farthest
标记了所有选择 [i..end]
中能够跳到的最远距离,jumps
记录了跳跃次数。
本算法的时间复杂度 O(N),空间复杂度 O(1),可以说是非常高效,动态规划都被吊起来打了。
至此,两道跳跃问题都使用贪心算法解决了。
其实对于贪心选择性质,是可以有严格的数学证明的,有兴趣的读者可以参看《算法导论》第十六章,专门有一个章节介绍贪心算法。这里限于篇幅和通俗性,就不展开了。
使用贪心算法的实际应用还挺多,比如赫夫曼编码也是一个经典的贪心算法应用。更多时候运用贪心算法可能不是求最优解,而是求次优解以节约时间,比如经典的旅行商问题。
不过我们常见的贪心算法题目,就像本文的题目,大多一眼就能看出来,大不了就先用动态规划求解,如果动态规划都超时,说明该问题存在贪心选择性质无疑了。
接下来可阅读:
_____________
《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「进群」可加入算法群;回复「全家桶」可下载配套 PDF 和刷题全家桶:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释