作者推荐
本文涉及知识点
LeetCode:403 青蛙过河
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 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
stones 按严格升序排列
动态规划
理论时间复杂度😮(nn)。
dp[i]记录所有能够从j跳到i的i-j，即k。
共有O(nn)种状态，故空间复杂度是O(nn)，每种状态的转移方程时间复杂度O(1)，故总时间复杂度O(nn)。
动态规划的细节，方便检查
| 动态规划的状态表示 | dp[i]记录所有能够从j跳到i的i-j，即k |
| 动态规划的转移方程 | 对于d[i]中的任意k，看是否存在石头stone[i]+i-1 ,stone[i]+i,stone[i]+i+1，如果存在，则可以跳到此石头。 |
| 动态规划的初始状态 | dp[0]不会被使用，所以不用初始化。dp[1]有一个元素1 |
| 动态规划的填表顺序 | i从小到大。因为只能从小到大跳，可以,确保动态规划的无后效性 |
| 动态规划的返回值 | dp.back()。size() |
超时代码
class Solution {
public:
bool canCross(vector& stones) {
if (1 != stones[1])
{
return false;
}
m_c = stones.size();
std::unordered_map<int, int> mValueIndex;
for (int i = 0; i < stones.size(); i++)
{
mValueIndex[stones[i]] = i;
}
vector<vector> dp(m_c);
dp[1].emplace_back(1);
for (int i = 1; i < m_c; i++)
{
for (const auto& k : dp[i])
{
for (int j = max(k - 1, 1); j <= k + 1; j++)
{
const int iNewValue = stones[i] + j;
if (mValueIndex.count(iNewValue))
{
dp[mValueIndex[iNewValue]].emplace_back(j);
}
}
}
}
return dp.back().size();
}
int m_c;
};
不超时代码
超时原因dp[i]中有重复值，用unorder_set除掉重复。
class Solution {
public:
bool canCross(vector& stones) {
if (1 != stones[1])
{
return false;
}
unordered_map<int, int> mPosToIndex;
for (int i = 2; i < stones.size(); i++)
{
mPosToIndex[stones[i]] = i;
}
vector<unordered_set> vPosK(stones.size());
vPosK[1].insert(1);
int k = 1;
for (int i = 1; i < stones.size(); i++)
{
if (stones.size() - 1 == i)
{
return vPosK[i].size();
}
for (auto& k : vPosK[i])
{
int iNewPos = stones[i] + k - 1;
if (mPosToIndex.end() != mPosToIndex.find(iNewPos))
{
vPosK[mPosToIndex[iNewPos]].insert(k - 1);
}
iNewPos++;
if (mPosToIndex.end() != mPosToIndex.find(iNewPos))
{
vPosK[mPosToIndex[iNewPos]].insert(k );
}
iNewPos++;
if (mPosToIndex.end() != mPosToIndex.find(iNewPos))
{
vPosK[mPosToIndex[iNewPos]].insert(k+1);
}
}
}
return true;
}
};
进阶除掉重复
重复的原因 ：dp[i]中有x1,x1+1,x1+2 。则x1+1 (x1+1) (x1+2)-1 三者重复。
当dp[j]中有重复的k，说明此时的i相同。由于k=j-i，i是严格递增的，所以k是递减的。由于k是有序的，所以相同的k是挨着一起的。只需要检查前一个元素是否相等，无需判断其它元素。可以在O(1)的时间中避免重复。
class Solution { public: bool canCross(vector<int>& stones) { if (1 != stones[1]) { return false; } m_c = stones.size(); std::unordered_map<int, int> mValueIndex; for (int i = 0; i < stones.size(); i++) { mValueIndex[stones[i]] = i; } vector<vector<int>> dp(m_c); dp[1].emplace_back(1); for (int i = 1; i < m_c; i++) { for (const auto& k : dp[i]) { for (int j = max(k - 1, 1); j <= k + 1; j++) { const int iNewValue = stones[i] + j; if (mValueIndex.count(iNewValue)) { auto& v = dp[mValueIndex[iNewValue]]; if (v.empty() || (v.back() != j)) { v.emplace_back(j); } } } } } return dp.back().size(); } int m_c; };
另外一种方法
前面的方法：第一层循环枚举i，第二层循环枚举k。
下面的方法：第一层循环枚举i，第二层循环枚举j。
class Solution { public: bool canCross(vector<int>& stones) { if (1 != stones[1]) { return false; } m_c = stones.size(); vector<unordered_set<int>> dp(m_c); dp[1].emplace(1); for (int i = 2; i < m_c; i++) { for (int j = 1 ; j < i ;j++ ) { const int iSub = stones[i] - stones[j]; if (dp[j].count(iSub - 1)|| dp[j].count(iSub)|| dp[j].count(iSub + 1) ) {//从够从stones[j]跳到stones[i] dp[i].emplace(iSub); } } } return dp.back().size(); } int m_c; };
