青蛙过河
解题思路:
最开始拿到题目,大致看了一眼,从第i个石块可以跳到别的石块上,问可不可以到最后一个,第一印象 想到了之前的最短路问题,但是后来仔细一看发现每一跳的距离都是动态改变的,而不是静态的数值,于是放弃了思想,转而考虑动态规划
动态规划状态分析:
- 状态$f[i][j]$表示的是能否从第i个石头往后跳j格
- 根据题目的先验条件,不难发现最开始只有$f[0][1] = 1$,其余的全部为0
状态转移:
- $f[i][j]$代表的是一个关于能否从第i个石头往后跳j格的bool值,那么如果要往后跳j格,那么它的前一跳必须是j-1格,即只要能够经过j-1跳到达第i个石头即可成功转移,伪代码如下:
if(可以经过"j-1跳"从某块石头到第i块石头)
说明f[i][j]是可以实现的,即f[i][j] = 1
那么我们要如何确定这某一块石头是哪一块呢?
我们假设某一块石头–>这一块石头的下标是k
1. 找到第i块石头的下标,即位于哪个坐标上
2. 因为从第k块石头经过 j - 1 步可以到第i块石头,所以定我们想要的第k块石头的位置即为 stones[i] - (j - 1)
那么我们要怎么确认这块目标石头是否存在呢?
因为在动态规划的过程中会不停的查看石头是否存在,所以我们可以通过哈希表的方式查找是否存在
if(hash.count(下标))
if(dp(下标,j-1))
成功找到
最后的解题代码如下:
超级大坑:在Leetcode平台上,千万不要在class外面声明$vector,queue$这类数据结构,否则结果没跑过都很莫名其妙!!!
const int N = 2010;
int f[N][N]; //f[i][j]数组存储的是从第i块石头是否可以往后跳j格的bool值,一开始默认为-1,表示没有搜索到过这个可能性,随着倒搜的进行,不断地更新f[i][j]数组。
class Solution {
public:
vector<int> p; //千万不要把这两个声明在class之外
unordered_map<int,int> h;
//这个函数是用于判断第i块石头能否往后跳j格
int dp(int i, int j){
if(f[i][j] != -1) return f[i][j]; //如果f[i][j]之前被搜过,就直接返回
f[i][j] = 0; //否则记录为跳不过去
for(int l = max(1, j - 1); l <= j + 1; l ++ ){ //向前继续搜,看更前面的石头是否满足条件
int x = p[i] - l; //找出上一跳的位置
if(h.count(x)){ //如果存在这么一块石头
int k = h[x];
if(dp(k,l)){
f[i][j] = 1;
break;
}
}
}
return f[i][j]; //搜完之后返回结果,不能直接返回true或者false
}
bool canCross(vector<int>& stones) {
p = stones;
memset(f, -1, sizeof f);
f[0][1] = 1;
int n = stones.size();
for(int i = 0; i < n; i ++ )
h[stones[i]] = i; //存下石头位置与下标的映射
for(int i = 0; i <= n; i ++ ){ //从第一个石头出发最多往后跳1位,依此类推,第n个石头最多往后跳n位,只需要判断第n个石头能否跳从0~n中的任意一个位数
if(dp(n - 1, i))
return true;
}
return false;
}
};
现在不是了,那道题被删了
重新修改了下题目链接~
。。。
???不是这个题的题解啊
是的鸭,https://www.acwing.com/activity/content/problem/content/3904/1/,这个是春季每日一题的