leetcode-403. 青蛙过河(动态规划|记忆化搜索)[通俗易懂]

leetcode-403. 青蛙过河(动态规划|记忆化搜索)[通俗易懂]一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2 )。如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k – 1、k 或 k + 1 个单位。 另请注意

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。

给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。

开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2 )。

如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k – 1、k 或 k + 1 个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。

示例 1:

输入:stones = [0,1,3,5,6,8,12,17]
输出:true
解释:青蛙可以成功过河,按照如下方案跳跃:跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后,跳 5 个单位到第 8 个石子(即最后一块石子)。
示例 2:

输入:stones = [0,1,2,3,4,8,9,11]
输出:false
解释:这是因为第 5 和第 6 个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。

提示:

2 <= stones.length <= 2000
0 <= stones[i] <= 231 – 1
stones[0] == 0

  1. 动态规划
    f[i][k]:代表在位置i,距离为j的时候是否可达,
    f[i][k] = f[i – 1][k – 1] | f[i – 1][k] | f[i – 1][k + 1]
    当第i个位置最多走i+1步
class Solution { 
   
public:
    bool canCross(vector<int>& stones) { 
   
        int n = stones.size();
        vector<vector<bool> >f(n + 1,vector<bool>(n + 1,false));
        f[0][0] = true;
        for(int i = 1;i < n;i ++){ 
   
            if(stones[i] - stones[i - 1] > i)return false;
        }
        for(int i = 1;i < n;i ++){ 
   
            for(int j = i - 1;j >= 0;j --){ 
   
                int dis = stones[i] - stones[j];
                if(dis > j + 1)break;
                f[i][dis] = f[j][dis - 1] | f[j][dis] | f[j][dis + 1];
                if(i == n - 1 && f[i][dis])return true;
            }
        }
        return false;
    }
};
  1. 记忆化搜索+暴力搜索
    dfs:已经走到了位置i,且跨越了距离dis
class Solution { 
   
public:

    int n;
    vector<unordered_map<int,bool> >mm;
    bool dfs(int u,int dis,vector<int>&stones){ 
   
        if(u == n - 1)return true;
        if(mm[u].find(dis) != mm[u].end())return mm[u][dis];
        for(int d = dis - 1;d <= dis + 1;d ++){ 
   
            int nowd = stones[u] + d;
            if(d <= 0)continue;
            int k = lower_bound(stones.begin(),stones.end(),nowd) - stones.begin();
            if(k < n && stones[k] == stones[u] + d && dfs(k,d,stones))return true;
        }
        return mm[u][dis] = false;
    }
    bool canCross(vector<int>& stones) { 
   
        n = stones.size();
        mm.resize(n + 1);
        if(n >= 2 && stones[1] != 1)return false;
        return dfs(1,1,stones);
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169125.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • HARQ发展_harq技术

    HARQ发展_harq技术自动重发请求含义,以及混合自动重发请求(包括Type-I,和CC-HARQ,IR-HARQ)的编译码方式。包括在传统HARQ的基础上衍生出来的时分复用,码分复用,功率域复用的HARQ

    2022年10月28日
  • ICMP报文的类型

    ICMP报文的类型ICMP经常被认为是IP层的一个组成部分。它传递差错报文以及其他需要注意的信息。ICMP报文通常被IP层或更高层协议(TCP或UDP)使用。一些ICMP报文把差错报文返回给用户进程。ICMP报文是在IP数据报内部被传输的,如图6-1所示。ICMP的正式规范参见RFC792[Posterl1981b]。ICMP…

  • TCP和UDP协议的区别_tcp和ip是什么意思

    TCP和UDP协议的区别_tcp和ip是什么意思最近在学习WebSocket,了解到它是采用TCP来实现异步通信,全双工.与Http不同的是,Http采用无状态,应答式的响应.因此就想知道TCP,TCP/IP,HTTP,Socket之间到底是有怎样的关联关系和区别,以及全双工通信和半双工通信是如何实现的在网络层.在计算机网络里,有两种常见的参考模型即:OSI参考模型和TCP/IP参考模型。由此可见TCP本身是传输层的协议,…

  • java 文件上传到服务器_Java上传文件到服务器端的方法「建议收藏」

    java 文件上传到服务器_Java上传文件到服务器端的方法「建议收藏」Web文件上传采用POST的方式,与POST提交表单不同的是,上传文件需要设置FORM的enctype属性为multipart/form-data.由于上传的文件会比较大,因此需要设置该参数指定浏览器使用二进制上传。如果不设置,enctype属性默认为application/x-www-form-urlencoded,使用浏览器将使用ASCII向服务器发送数据,导致发送文件失败。上传文件要使用文件…

  • Datagrip2021.8.3激活码【中文破解版】[通俗易懂]

    (Datagrip2021.8.3激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlS3…

  • 多线程(二)—-线程的启动方式(一)

    多线程(二)—-线程的启动方式(一)

    2020年11月12日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号