【动态规划】【数学】【C++算法】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 <= 10⁴

这题太难了，反复看各位大佬的题解。结合自己的思考，总结出适合中国人理解的解法。

由于空格消失，故用_代替。

原理

令S=A^k1RA^k2…R^kn 表示dp[x]的最短指令序列,x的取值范围(0,target]。Aⁿ 代替n个A,n可以为0。定义S1,S2,S4,使得 S == R^k1+S1 S == R^k1R + S2 S == A^k1RA^k2R+S4 。dp[x]的含义：当前速度为1，向当前方向行驶x的最短指令序列的长度。

S有如下性质：

一，一定不会以R结尾。假定以R结尾，删除它。距离不变。

二，一定不会以R开头。 否则删除RA^k1R ，再在末尾增加 RRA^k1或RA^k1，指令长度不变或变短。

三,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顶多出现一次。否则将第一个A^ki变成A^ki+1,第二个A^ki删除，末尾追加RRA或RA。

七，如果ki等于1。则最多出现2次。否则将三个A，变成A² A⁰ A⁰。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等于2^k，则最短指令就是A^k。每一步都是最大加速，最大移动距离。

十一，假定某段指令的k1为x，则此指令的最大行驶距离vMaxDis(x)为（正方向全部选择，负方向全部不选择）：

x == 0,最大行驶距离0。

x== 1，2个A最大行驶距离为2。

x== 2，当有两个AA时，不会再有A，故最大行驶距离为6。AA_AA_ A -> AAA 5个字符变3个字符。只能AA A_A 行程5，AA_AA 行程6。
x== 3 当两个AAA存在时，不会存在A或AA，最大行驶距离：14。AAA AAA_ A => AAAA 7个字符变4个字符 AAA _AAA AA => AAAA A A 8个字符变6个字符。2个AAA的行程是14。其它组合不会超过14。
x==4 1个A AA …A^x 。和为:Sumi = 1 : x _{i=1}^{:x}i=1:x(2ⁱ-1) = Sumi = 1 : x _{i=1}^{:x}i=1:x(2ⁱ)-x = 2^(x+1)-2- x 。A _AA AAA 做特殊处理，删除A AA _AAA ，加上14，即 - 11+14 ， 2^(x+1)-2- x+3= 2^(x+1) - x +1

十二，假定某段指令的k1为x，则k2的最大值为vK2Max(k1)：

根据性质四,k2一定不等于k1。

根据性质五，如果x>=3，则k2一定不是x-1，也不是x+1。

如果x >= 3，k2>=x+2 无论如何都会让行驶的距离为负

k1行驶的路程-k2行驶的路径+ vMaxDis(k1) = 2^k1-2^(k1+2) + 2^(k1+1)-k1+1 = -2^k1-k1 + 1 路程恒定为负，淘汰。

综上所述：x>=3 k2的最大值为x-2。

k1为0，无意义。

k1为1，k2最大为0；如果k2为1，和k1抵消；如果k2为2，则行驶的总距离一定为负。

k1为2，k2可以为1。h1为2时，最大正方向为6。h2为3的话，负方向至少为7。总行程必定为负。故h2最大为1。

h2一定小于h1。

十三：假定某段指令的k1为x，则最小行驶距离vMinDis(x)（除k1外，正方向全部不选，负方向全选）为

故：vMinDis(x) = 2^x-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]的x必须在区间[0,x)

动态规划的转移方程

根据上面的十余条性能，可以淘汰很多指令系列。我们只需要计算dp[x]，x取值范围[1,target]如果无法表示此范围的行程，也淘汰掉。

由于是从小到大计算x，转移方程中用到的dp[y] ,y的取值范围必须是[0,x)，否则无法保证无后效性。

则 S1 行驶的路程为: x - (2^k1-1)

S2 行驶的路程为：y = (2^k1-1) - x

如果y == 0 , 直达 dp[x] = k1

如果 y 取值[0,x） dp[x] = k+1 + dp[y] 如果S2有更短的指令，替换S2，则S更短

如果 y >= x ， 抛弃，见下面的证明一。

如果y < 0

枚举h2，已证明h2 >=0 且 h2 < h1。

令y1是S4行驶的总路程。

令y1 =x - （ 2^k1-1）+ (2^k2-1) = x - 2^k1+2^k2

由于k1 > k2 ，所以 y1 < x

y < 0 ==>> x - 2^k1+1 > 0

k2的最小值为0，故2^k2的最小值为1 故 y1 > 0 。

由于y1取值范围(0,x) 无法到x，故h3必定存在。

可以这样理解：向前走了一段没到目标，向后走了一段（小于向前的距离，且大于等于0）。必定不会到达目标，也不会回到起点。

dp[y1]对应的指令串就是S4，否则替换S4，S会变短。

证明一：2^k1-1 != 2x。
如果两者相等，则直接用S2代码代替S，更短。
证明二：2^k1-1 不大于 2x。

假定2^k1-1 > 2x 也就是2^k1-1 >= 2x +1 ==>>> 2^k1 >= 2*(x+1) ===>>> 2^k-1 >= x+1 式子一

以A^k2开头的S2，必须能等于 2^k1-1 - x ,

a，k1 >= 4 假设一

根据性质五,h2 <= k1-2

S2的最大路程为：

2^(x+1) - x +1

将k1-2 代替x

2^k1-1- (k1-2)+1 = 2^k1-1-k1+3

假定S2的最大路程能>=y：

2^k1-1-k1+3 >= 2^k1-1 - x

-k1+3 >= 2^k-1 -1 - x

x+4 >= 2^k-1 +k1 假设二

式子一和假设一

===>>> 2^k-1 +k1 >= x+5 ==>>> 2^k-1 +k1 > x+4 ==》 x+4 < 2^k-1 +k1 式子二

假设二和式子二矛盾

b:k1 <= 3

k1等于0，总路程小于等于0，无意义。

k1等于1，k2为0。h2 h4 h6是递减的，如果h2为0,则h2 h4 h6…全部为0，也就是没有返程。没有返程意味者k1走的路程 <= x。

k1等于2，k2为1。k1的路程为3，只有当x1=1，才符合3>2*x。x=1的时候，最短距离是A。显然k1不等于2。h2为0同上。

k1等于3,k1的路程为7，只有x等于1 2 3 才符合，最短串分别为 A ARRA(或AARA) AA 。 k1都不为3。

代码

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

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  {
    Solution sln;
    vector<int> ans = { 1,4,2,5,7,5,3,6,8,7,10,7,9,6,4,7,9,8,11,12,10,9,12,9,11,13,11,8,10,7,5,8,10,9,12
              ,13,11,10,13,15,14,15,13,14,12,11,14,11,13,16,14,17,14,15,13,10,12,14,12,9,11,8,
              6,9,11,10,13,14,12,11,14,16,15,16,14,15,13,12,15,17,16,19,19,18,17,18,16,18,18,17,15,16,14,13,16,13,15,18,16,19
    };
    for (int i = 0; i < 100; i++)
    {
      auto res = sln.racecar(i + 1);
      Assert(res, ans[i]);
    }   
  }
  {
    Solution sln;
    vector<int> ans = { 45, 43, 40, 41, 43, 42, 44, 43, 44, 42, 39, 40, 42, 41, 38, 39, 37, 34, 36, 39, 37, 40, 42, 40, 38, 41, 43
      , 42, 45, 42, 44, 41, 39, 42, 44, 43, 46, 47, 45, 44, 47, 44, 46, 48, 46, 43, 45, 42, 40, 43, 45, 44, 47, 48, 46, 45, 48, 50, 49, 50, 48, 49, 47, 46, 49, 46, 48, 51, 49, 52, 49, 50, 48, 45, 47, 49, 47, 44, 46, 43,
      41, 44, 46, 45, 48, 49, 47, 46, 49, 51, 50, 51, 49, 50, 48, 47, 50, 52, 51, 54 };
    for (int i = 0; i < 100; i++)
    {
      auto res = sln.racecar(10000-i);
      Assert(res, ans[i]);
    }
  }
}

附录：

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_target2 ))

{

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();

}

};