【动态规划】C++算法:403.青蛙过河

2024-01-09 17:59:34

作者推荐

【动态规划】C++算法312 戳气球

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;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+

+17**
如无特殊说明,本算法用**C++**实现。

文章来源:https://blog.csdn.net/he_zhidan/article/details/135435982
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。