专栏首页Michael阿明学习之路LeetCode 403. 青蛙过河(DP)

LeetCode 403. 青蛙过河(DP)

1. 题目

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

给定石子的位置列表(用单元格序号升序表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一个石子上)。 开始时, 青蛙默认已站在第一个石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格1跳至单元格2)。

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

请注意: 石子的数量 ≥ 2 且 < 1100; 每一个石子的位置序号都是一个非负整数,且其 < 231; 第一个石子的位置永远是0。

示例 1:
[0,1,3,5,6,8,12,17]
总共有8个石子。
第一个石子处于序号为0的单元格的位置, 第二个石子处于序号为1的单元格的位置,
第三个石子在序号为3的单元格的位置, 以此定义整个数组...
最后一个石子处于序号为17的单元格的位置。
返回 true。即青蛙可以成功过河,按照如下方案跳跃: 
跳1个单位到第2块石子, 然后跳2个单位到第3块石子, 接着 
跳2个单位到第4块石子, 然后跳3个单位到第6块石子, 
跳4个单位到第7块石子, 最后,跳5个单位到第8个石子(即最后一块石子)。

示例 2:
[0,1,2,3,4,8,9,11]
返回 false。青蛙没有办法过河。 
这是因为第5和第6个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/frog-jump 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 动态规划

  • dp数组,存储一个set,set中存储前一格是跳多少步step过来的(可能有多种方案,需要去除同样步数过来的)
  • 走到一格以后,根据当前step,向前试探 k-1,k,k+1 步,看在不在石头上
  • 在石头上,则将走的步数插入到该位置的集合中
class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int,int> m;//存储distance、对应的下标
        int i, j, k, n = stones.size(), len;
        if(stones[1] != 1)//题目意思是,第一步只能走1个distance
            return false;
        for(i = 0; i < n; ++i) 
        	m[stones[i]] = i;
        // int dp[n] = {0};//存储到达一块石头时,一次跨多少步过来的(不可以用一维数组)
        vector<unordered_set<int>> dp(n);//可能有多种跳到过来的方法,对后面的k有影响
        unordered_set<int>::iterator it;
        dp[1].insert(1);
        int delta[3] = {-1,0,1};//前进的增量
        int distance, step;
        for(i = 1; i < n; ++i)
        {
        	len = dp[i].size();
            if(len > 0)//跳过来的方案数存在
            {
                for(j = 0; j < 3; ++j)//每个方案有3种增量前进
                {
                	for(it = dp[i].begin(); it != dp[i].end(); ++it)
                	{	//遍历每个方案(前面多少步跳过来的)
	                	step = *it+delta[j];
	                	distance = stones[i]+step;//可到的距离
	                    if(step > 0 && m.count(distance))//方向是向前的,且 在石头上
	                        dp[m[distance]].insert(step);//将多少步过去的记录在那个石头上
	                }
                }
            }
        }
        return dp[n-1].size()>0;//有方案可以到达最后一个石头
    }
};

别人的解法总是这么优雅

class Solution {
public:
    bool canCross(vector<int>& stones) {
        bool dp[1101][1101];//dp[位置][步长],表示第i个石头,步长,可以到它那里吗
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        int gap, i;
        for(i = 1; i < stones.size(); i++) 
        {
            for(int j = 0; j < i; j++) 
            {
                gap = stones[i] - stones[j];//前面的石头跟我比有多远
                if(gap >= 1100) continue;
                if(dp[j][gap] || dp[j][gap + 1] || (gap > 0 && dp[j][gap - 1]))
                    dp[i][gap] = true;
            }
        }
        for(i = 0; i < stones.size(); i++)
            if(dp[stones.size() - 1][i])
                return true;
        return false;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1049. 最后一块石头的重量 II(DP)

    每一回合,从中选出任意两块石头,然后将它们一起粉碎。 假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

    Michael阿明
  • LeetCode 276. 栅栏涂色(DP)

    有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏,每个栅栏柱可以用其中一种颜色进行上色。

    Michael阿明
  • LeetCode 44. 通配符匹配(DP)

    给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。

    Michael阿明
  • Excel这样分奖金

    有朋友问我如何能将下面的表分奖金~ ? 其实我内心是拒绝的~ 要是我的名字在里面,我会很开心的帮他做的,然而,并没有! 有激励金额,还有百分比,两者直接相乘...

    用户1332619
  • 活动丨腾讯云通信多款产品优惠大来袭!

    ? ? 福利到! 腾讯云通信针对首次购买实时音视频的客户 即可获赠 10000分钟免费通话时长! 腾讯云通信产品优惠“享不停” ? 腾讯云通信致力于搭建专业、...

    腾讯即时通信IM
  • Python小练:爬取豆瓣影评,看一部电影到底在讲什么?

    Python的强大,可能在于能做好玩的事情,比如知乎上有关python最火的回答,就是分享怎么用python画出世界名画的赶脚。

    养码场
  • 我爬取豆瓣影评,告诉你《复仇者联盟3》在讲什么?

    复联 3 作为漫威 10 年一剑的收官之作。漫威确认下了很多功夫, 给我们奉献一部精彩绝伦的电影。自己也利用周末时间去电影院观看。看完之后,个人觉得无论在打斗特...

    猴哥yuri
  • 商城项目-队列改造项目

    这里没有指定交换机,因此默认发送到了配置中的:leyou.item.exchange

    cwl_java
  • Kotlin-Android的另一番风味

    微信 订阅号助手 的Android App项目首次尝试使用Kotlin进行大规模的业务开发(483个Kt文件,3.8W行不包含空行的Kt代码),一开始接触Ko...

    微信终端开发团队
  • MySQL库表设计小技巧

    在我们项目开发中,数据库及表的设计可以说是非常重要,我遇到过很多库表设计比较杂乱的项目,像表名、字段名命名混乱、字段类型设计混乱等等,此类数据库后续极难维护与拓...

    MySQL技术

扫码关注云+社区

领取腾讯云代金券