【动态规划】【数学】【C++算法】18赛车

发布时间:2024年01月18日

作者推荐

视频算法专题

本文涉及知识点

动态规划 数学

LeetCode818赛车

你的赛车可以从位置 0 开始,并且速度为 +1 ,在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 ‘A’ 和倒车指令 ‘R’ 组成的指令序列自动行驶。
当收到指令 ‘A’ 时,赛车这样行驶:
position += speed
speed *= 2
当收到指令 ‘R’ 时,赛车这样行驶:
如果速度为正数,那么speed = -1
否则 speed = 1
当前所处位置不变。
例如,在执行指令 “AAR” 后,赛车位置变化为 0 --> 1 --> 3 --> 3 ,速度变化为 1 --> 2 --> 4 --> -1 。
给你一个目标位置 target ,返回能到达目标位置的最短指令序列的长度。
示例 1:
输入:target = 3
输出:2
解释:
最短指令序列是 “AA” 。
位置变化 0 --> 1 --> 3 。
示例 2:
输入:target = 6
输出:5
解释:
最短指令序列是 “AAARA” 。
位置变化 0 --> 1 --> 3 --> 7 --> 7 --> 6 。
提示:
1 <= target <= 104
这题太难了,反复看各位大佬的题解。结合自己的思考,总结出适合中国人理解的解法。

动态规划

用An 代替n个A,n可以为0。则任何指令流可以表示为:
Ak1RAk2…Rkn 。有如下性质:
一,一定不会以R结尾。假定以R结尾,删除它。距离不变。
二,一定不会以R开头。 否则删除RAk1R ,再在末尾增加 RRAk1或RAk1,指令长度不变或变短。如果R的数量偶数,则加RA,指令少一个字符。如果R的数量是奇数,则加RRA,指令不变。
三,ki的i为奇数,则是正方向;i为偶数,则是反方向。如果x1和x2奇偶性相同,则交换kx1和kx2,行驶的路程不变。对奇数ki按降序排序,对偶数ki按降序排序。
四,x1和x2奇偶性不同。则kx1一定不等于kx2,否则通过性质三,移到最后然后删除。
五,x1和x2奇偶性不同。kx1>=3 ,则kx1一定不等于kx2+1,否则kx1变kx2,kx2变0,末尾加RA或RRA。
六,如果ki>=4,则ki顶多出现一次。否则将第一个Aki变成Aki+1,第二个Aki删除,末尾追加RRA或RA。
七,如果ki等于1。则最多出现2次。否则将三个A,变成A2 A0 A0。3个字符变2个字符。
八,如果ki等于2。则最多出现2次。否则将三个AA 变成A^3 A A。6个字符变5个字符。
九,如果ki等于3。则最多出现2次。否则将三个AAA变成,A^4 A^2 A^2。9个字符变8个字符。
十,如果x+1等于2k,则最短指令就是Ak。每一步都是最大加速,最大移动距离。
十一,假定某段指令的k1为x,则此指令的最大行驶距离vMaxDis(x)为(正方向全部选择,负方向全部不选择):
x== 0,最大行驶距离0。
x== 1,2个A最大行驶距离为2。
x== 2,2个A 2个AA,最大行驶距离为8。
x== 3 2个A AA AAA ,最大行驶距离:22。
x== 4 1个A AA …Ax 外加1个A AA AAA 。前者和为:Sum i = 1 : x _{i=1}^{:x} i=1:x?(2i-1) = Sum i = 1 : x _{i=1}^{:x} i=1:x?(2i)-x = 2^(x+1)-2- x 。后者和为:11。两者之和:2^(x+1)-2- x + 11
十二,假定某段指令的k1为x,则k2的最大值为vK2Max(k1):
根据性质四,k2一定不等于k1。
根据性质五,如果x>=3,则k2一定不是x-1,也不是x+1。
如果x==3,k2>=x+2 无论如何都会让行驶的距离为负
8-32+(22-7) = -9
如果k=x+2 x>=4 无论如何 都会让行驶的路程为负。
2x-1 -( 2^(x+2)-1) + vMaxDis(x) = vMaxDis(x)-2x*3 = -2x-2-x +11,令x=4 -16-2-4+11 < 0。
综上所述:x>=3 k2的最大值为x-2。
k1为0,无意义。
k1为1,k2最大为0;如果k2为1,和k1抵消;如果k2为2,则行驶的总距离一定为负。
k1为2,k2可以为3。h2为3只有一种可能,正方向AA AA A A 负方向AAA。总路程1。而dp[1]的最短路程显然是1,即A。排除此特例后 h2为1。
排除特例后,h2一定小于h1
十三:假定某段指令的k1为x,则最小行驶距离vMinDis(x)(除k1外,正方向全部不选,负方向全选)为
故:vMinDis(x) = 2x-1 - vMaxDis(vK2Max(x))

vMinDis的计算值大于实际值,动态规划时可能会有遗漏造成错误。小于实际值,只会多计算几次,不会造成错误。故为了简化问题:令vMinDis(1)和vMinDis(2)等于0。

实现

初始化时计算vK1,如果vK1[x]记录符合以下条件的k1。vMinDis(k1) <= x 且vMaxDis(k1)>=x。
动态规划的状态表示,则初始速度为1,向当前方向行驶x的最短指令流为dp[x]。动态规划的初始值dp[0]=0。
动态规划的填表顺序:
第一层循环: 从1到大枚举x。
第二层循环:枚举可能k1。
第三层循环: 枚举可能的k2。
动态规划的返回值:dp.back()。
难点 dp[x]不能为负数:

动态规划的转移方程

如果k1 越过x ,令x2= 2k1-1 - x ,dp[x] = k+1 + dp[x2]
如果x2 >= x 忽略。原因:k1>k2。则vMaxDis[k1] > vMaxDis[k2]。
如果k1没有越过x,如果有k3
则 dp[x] = k1+1 + k2+1 + dp[?]
如果没k3则
dp[x] = k1+1 + k2;

代码

class Solution {
public:
	int racecar(int target) {
		auto K2Max = [](int k1)
		{
			static vector<int> v = { 0,0,1 };
			return k1 >= v.size() ? k1 - 2 : v[k1];
		};
		vector<int> vMaxDis = { 0 } ,vMinDis = { 0 };
		for (int k1 = 1; ; k1++)
		{
			int iMax = (1 << (k1 + 1)) - 2 - k1 ;
			if (1 == k1)
			{
				iMax += 1;
			}
			else if(2 == k1)
			{
				iMax += 4;
			}
			else
			{
				iMax += 11;
			}
			const int iMin = (1 << k1) - 1 - vMaxDis[K2Max(k1)];
			if (iMin > 10000)
			{
				break;
			}
			vMaxDis.emplace_back(iMax);
			vMinDis.emplace_back(iMin);
		}

		vector<vector<int>> vK1(target + 1);
		for (int i = 1; i < vMaxDis.size(); i++)
		{
			for (int x = max(1, vMinDis[i]); x <= min(target, vMaxDis[i]); x++)
			{
				vK1[x].emplace_back(i);
			}
		}
		vector<int> dp(target + 1, 100'000);
		dp[0] = 0;
		for (int x = 1; x <= target; x++)
		{
			for (const auto& k1 : vK1[x])
			{
				const int iRemain = (1 << k1) - 1 - x;
				if ( 0 == iRemain )
				{
					dp[x] = k1;//只有k1
					break;
				}
				if (iRemain > 0)
				{	
					if (iRemain < x)
					{
						dp[x] = min(dp[x], k1 + 1 + dp[iRemain]);//超出部分
					}
					continue;
				}
				for (int k2 = 0; k2 <= K2Max(k1); k2++)
				{
					const int iNewX = x - (1 << k1) + (1 << k2);//iNew为0,有k2无k3
					if (iNewX < 0)
					{
						assert(false);
					}
					else
					{
						dp[x] = min(dp[x], k1 + k2 + 1 + (0 != iNewX) + dp[iNewX]);
					}
				}
			}
		}
		return dp.back();
	}
};

附录:
k1:1 minDis:1 maxDis:2
k1:2 minDis:1 maxDis:8
k1:3 minDis:5 maxDis:22
k1:4 minDis:7 maxDis:37
k1:5 minDis:9 maxDis:68
k1:6 minDis:26 maxDis:131
k1:7 minDis:59 maxDis:258
k1:8 minDis:124 maxDis:513
k1:9 minDis:253 maxDis:1024
k1:10 minDis:510 maxDis:2047
k1:11 minDis:1023 maxDis:4094
k1:12 minDis:2048 maxDis:8189
k1:13 minDis:4097 maxDis:16380
k1:14 minDis:8194 maxDis:32763

2023年1月版

class Solution {
public:
bool AddQue(int(vHasDisSpeed)[41], vector<std::pair<int, int>>& qDisSpeed, int iDis, int iSpeed, int iOpeNum)
{
iSpeed += 20;
if ((iDis < 0) || (iDis >= m_target
2 ))
{
return false;
}
if (INT_MAX != vHasDisSpeed[iDis][iSpeed])
{//已经处理
return true;
}
vHasDisSpeed[iDis][iSpeed] = iOpeNum;
qDisSpeed.emplace_back(iDis, iSpeed);
return true;
}
int racecar(int target) {
m_target = target;
int vHasDisSpeedOpeNum[10000 * 2][41] = { INT_MAX };
for (int i = 0; i < sizeof(vHasDisSpeedOpeNum) / sizeof(vHasDisSpeedOpeNum[0]); i++ )
for (int j = 0; j < sizeof(vHasDisSpeedOpeNum[0]) / sizeof(vHasDisSpeedOpeNum[0][0]); j++)
{
vHasDisSpeedOpeNum[i][j] = INT_MAX;
}
vector<std::pair<int, int>> qDisSpeed;
AddQue(vHasDisSpeedOpeNum, qDisSpeed, 0, 1, 0);
for (int i = 0; i < qDisSpeed.size();i++ )
{
int iDis = qDisSpeed[i].first;
const int iOpeNum = vHasDisSpeedOpeNum[iDis][qDisSpeed[i].second];
int iSpeedK = qDisSpeed[i].second - 20;
int iSpeed = 1 << (abs(iSpeedK)-1);
if (iSpeedK < 0)
{
iSpeed *= -1;
}
if (iDis + iSpeed == target)
{
return iOpeNum + 1;
}
AddQue(vHasDisSpeedOpeNum, qDisSpeed, iDis + iSpeed, iSpeedK > 0 ? iSpeedK + 1 : iSpeedK - 1, iOpeNum + 1);
AddQue(vHasDisSpeedOpeNum, qDisSpeed, iDis, iSpeedK > 0 ? -1 : 1, iOpeNum + 1);
}
return -1;
}
int m_target;
};

2023年8月版

class Solution {
public:
int racecar(int target) {
if (1 == target)
{
return 1;
}
if (2 == target)
{
return 4;
}
vector dp(target + 1,INT_MAX);
dp[1] = 1;
dp[2] = 4;
int k = 1;
for (int i = 3; i <= target ;i++ )
{
while ((1 << (k + 1)) <= i+1)
{
k++;
}
{
const int first = (1 << k) - 1;
if (first == i)
{
dp[i] = k;
continue;
}
for (int j = 0; j < k; j++)
{
dp[i] = min(dp[i], k + 1 + j + 1+ dp[i - first + (1 << j )-1]);
}
}
{
const int first = (1 << (k+1)) - 1;
dp[i] = min(dp[i], (k + 1) + 1 + dp[first - i]);
}
}
return dp.back();
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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/135657282
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。