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

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(54)落宝金钱寻最优 - 跳跃游戏(贪心策略)

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(54)落宝金钱寻最优 - 跳跃游戏(贪心策略)

哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的落宝金钱谷,谷中有一条长长的石板路,每块石板上刻有数字,代表哪吒在此处可获得的灵力值。谷口有一块巨大的石碑,上面刻着一行文字:“欲破此谷,需以落宝金钱之力,寻最优跳跃路径,贪心策略显真身。”

哪吒定睛一看,石碑上还有一行小字:“数组[2, 3, 1, 1, 4]表示每块石板上的灵力值,哪吒从第一块石板出发,每次跳跃最远可跳至灵力值所指示的下一块石板,最终能否到达最后一块石板?”哪吒心中一动,他知道这是一道关于跳跃游戏的难题,需要通过贪心策略来找到最优跳跃路径。

暴力解法:落宝金钱的初次尝试

哪吒心想:“要判断能否到达最后一块石板,我可以逐个石板尝试跳跃。”他催动落宝金钱之力,从第一块石板开始,逐个石板跳跃,试图找到一条到达终点的路径。

bool canJump(vector<int>& nums) {
   
    int n = nums.size();
    vector<bool> dp(n, false);
    dp[0] = true;
    for (int i = 0; i < n; ++i) {
   
        if (dp[i]) {
   
            for (int j = 1; j <= nums[i]; ++j) {
   
                if (i + j < n) {
   
                    dp[i + j] = true;
                }
            }
        }
    }
    return dp[n - 1];
}

哪吒成功地判断了能否到达最后一块石板,但落宝金钱的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当石板数量很多时,灵力消耗巨大。

C++语法点

在C++中,跳跃游戏问题涉及到数组的遍历和贪心策略。以下是一些重要特性:

  • 数组遍历

    • 使用for循环遍历数组。
    • 常用操作:
      • nums[i]:访问数组中的元素。
  • 贪心策略

    • 通过维护最远可达位置,避免逐个石板尝试。

高阶优化:贪心策略的智慧

哪吒元神中突然浮现金色铭文——「落宝金钱寻最优,贪心策略显真身」。他意识到,可以通过贪心策略优化跳跃游戏的判断过程。

哪吒决定使用贪心策略,维护一个最远可达位置maxReach,每次跳跃时更新maxReach,如果当前石板的索引超过maxReach,则无法继续跳跃。通过这种方式,他成功地判断了能否到达最后一块石板,而且灵力消耗大幅减少。

bool canJump(vector

http://www.kler.cn/a/586549.html

相关文章:

  • 洛谷 P1068 [NOIP 2009 普及组] 分数线划定 python
  • 【Kubernets】Deployment 和 StatefulSet 有什么区别?什么时候用 StatefulSet?
  • 内存泄漏的防范:检测与预防
  • 稳定运行的以Oracle数据库为数据源和目标的ETL性能变差时提高性能方法和步骤
  • Windows下安装MongoDB 8
  • 星越L_电动车窗使用及初始化讲解
  • [数据结构]排序之 直接选择排序
  • pytest快速入门 - 目录:半天掌握pytest
  • 数据结构(泛型)
  • OracleCdc和MysqlCdc区别详解
  • 【一句话经验】ubuntu vi/vim 模式自动设置为paste
  • VBA+FreePic2Pdf 找出没有放入PDF组合的单个PDF工艺文件
  • 【CF】Day7——Codeforces Round 919 (Div. 2) BC
  • 表单 schema 配置化
  • L3-1 夺宝大赛
  • Manus 一码难求,MetaGPT、OpenManus、Camel AI 会是替代方案吗?
  • MESH网络技术解析
  • Ant Design Vue UI框架快速打造后台管理管理案例
  • K8S学习之基础三十:k8s中RBAC 的核心概念
  • 华为OD机考真题 Linux 发行版的数量(Java)