LeetCode 算法：跳跃游戏 c++

一九九一晚春

1402人浏览 · 2024-08-21 22:52:23

一九九一晚春 · 2024-08-21 22:52:23 发布

原题链接🔗：跳跃游戏
难度：中等⭐️⭐️

题目

给你一个非负整数数组 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 <= 10⁴
0 <= nums[i] <= 10⁵

动态规划

动态规划（Dynamic Programming，简称DP）是一种算法思想，用于解决具有重叠子问题和最优子结构特性的问题。它通过将问题分解为更小的子问题，并存储这些子问题的解（通常是在表格中），来避免重复计算，从而提高算法效率。

动态规划的关键步骤：

识别子问题：将原问题分解为一系列子问题，这些子问题通常是原问题规模更小的版本。
确定状态：定义状态变量，通常用一个或多个变量来表示问题的某一阶段的状态。
状态转移方程：找到状态之间的关系，即当前状态是如何由之前的一个或多个状态推导出来的。
确定边界条件：确定递推的起始点，也就是基本情况（base case）。
计算顺序：确定计算状态的顺序，以确保在计算当前状态之前，所需的所有状态都已经被计算过。
构造最优解：根据状态转移方程和边界条件，从基本情况开始，逐步构建解决方案。

动态规划的类型：

自顶向下的递归方法（Memoization）：从原问题开始，逐步分解为子问题，使用递归计算，并存储已经计算过的子问题的结果以避免重复计算。
自底向上的迭代方法：从基本情况开始，逐步向上计算直到原问题的状态，通常使用循环和表格来实现。

动态规划的应用领域：

优化问题：如最短路径、最小花费、最大收益等。
计数问题：计算不同选择的数量。
组合问题：如切割问题、背包问题等。

示例：斐波那契数列（自底向上方法）

斐波那契数列是一个经典的动态规划问题，可以通过以下步骤解决：

状态定义：F(n) 表示斐波那契数列的第 n 项。
状态转移方程：F(n) = F(n-1) + F(n-2)。
边界条件：F(0) = 0，F(1) = 1。
计算顺序：从 n = 2 到 n。
代码实现：

int fibonacci(int n) {
    if (n <= 1) return n;
    int dp[n + 1]; // 创建一个大小为 n+1 的数组
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

动态规划是一种强大的算法设计技术，适用于解决许多类型的问题。掌握动态规划需要大量的练习和对问题结构的深入理解。

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法不保证会得到最优解，但在某些问题中，贪心算法的解是足够好的，或者在性能上是可接受的。

贪心算法的关键特点：

贪心选择性质：在每一步选择中都采取当前状态下的最优选择。
无回溯：一旦进行选择，就不再回溯，即不重新考虑之前的选择。
子问题最优：局部最优选择可能导致全局最优解。
可行性：选择的每一步必须是可行的。

贪心算法的适用场景：

当问题具有最优子结构时，即问题的最优解包含子问题的最优解。
当问题可以通过贪心选择性质来解决时。

贪心算法的步骤：

问题定义：明确问题的目标和约束条件。
贪心选择：确定每一步的贪心选择标准。
可行性检验：确保每一步的选择都是可行的。
构造解决方案：按照贪心选择逐步构造解决方案。

示例：硬币找零问题

假设有无限数量的硬币，面额分别为1元、2元和5元，需要找零金额为n元。贪心算法的思路是尽可能多地使用面额最大的硬币。

贪心选择：尽可能多地使用5元硬币。
状态更新：剩余金额减去5元硬币的面额。
重复：直到剩余金额小于5元。
继续贪心选择：然后尽可能多地使用2元硬币。
最终：使用1元硬币补足剩余金额。

代码实现：

#include <iostream>
#include <vector>

void coinChange(std::vector<int>& coins, int n) {
    int count = 0;
    for (int i = coins.size() - 1; i >= 0; --i) {
        count += n / coins[i];
        n %= coins[i];
    }
    std::cout << "Minimum coins needed: " << count << std::endl;
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    coinChange(coins, 11); // 输出应该是 3 (5 + 5 + 1)
    return 0;
}

贪心算法简单且易于实现，但在使用时需要仔细考虑问题是否适合使用贪心策略。有些问题，如旅行商问题（TSP）或背包问题（Knapsack Problem），贪心算法可能无法得到最优解，而需要使用动态规划或其他更复杂的算法。

题解

解题思路：

LeetCode 上的 “跳跃游戏” 问题是一个典型的动态规划问题。这个问题的描述是：给定一个非负整数数组，表示每个位置可以跳跃的最大长度，判断从数组的开始位置出发，能否到达数组的最后一个位置。

问题背景
假设有一个数组 nums，其中 nums[i] 表示从位置 i 可以跳到 i + nums[i] 的位置。如果 i + nums[i] 大于或等于数组的长度，则表示可以跳出数组。

解题思路

贪心算法：这是解决这个问题的一种方法。我们可以从数组的开始位置开始，每次跳到能够到达的最远位置。然后，从这个新位置继续这个过程，直到到达或超过数组的最后一个位置。

动态规划：另一种方法是使用动态规划。我们可以创建一个布尔数组 dp，其中 dp[i] 表示从位置 i 是否能够到达数组的末尾。然后，我们可以从后向前填充这个数组，因为我们知道从最后一个位置可以到达末尾。

一次遍历：在贪心算法的基础上，我们可以进一步优化，只进行一次遍历。我们维护两个变量，maxReach 表示当前能够到达的最远位置，end 表示数组的末尾。在遍历过程中，如果当前位置加上可以跳的距离大于 maxReach，则更新 maxReach。如果 maxReach 大于或等于 end，则表示可以到达末尾。

c++ demo：

#include <iostream>
#include <vector>

bool canJump(std::vector<int>& nums) {
    int maxReach = 0, i = 0;
    while (i < nums.size()) {
        if (i > maxReach) return false; // 如果当前索引超过了能到达的最远距离，则无法到达末尾
        maxReach = std::max(maxReach, i + nums[i]); // 更新能到达的最远距离
        i++; // 移动到下一个可以跳的位置
    }
    return true; // 如果遍历完成，说明可以到达末尾
}

int main() {
    std::vector<int> nums1 = { 2, 3, 1, 1, 4 };
    std::cout << (canJump(nums1) ? "true" : "false") << std::endl; // 应该输出 true

    std::vector<int> nums2 = { 3, 2, 1, 0, 4 };
    std::cout << (canJump(nums2) ? "true" : "false") << std::endl; // 应该输出 false

    std::vector<int> nums3 = { 0 };
    std::cout << (canJump(nums3) ? "true" : "false") << std::endl; // 应该输出 true

    return 0;
}