题解 | #小招喵跑步#(动态规划)c++

分析

首先这题第一反应就是和青蛙过河有点类似，但是这题可以越过x，而且可能为负数，所以思路是首先将题目降为青蛙过河问题，只能向前走，跳过有且只能跳过一次，因此我们可以使用动态规划的思路。

问题降维

首先我们希望小招只能往前走，而且不论x到底为正为负都不会影响最终结果，我们将其置为正

input = abs(input);

递推公式

首先我们可以另数组dp的每个值为跳到当前位置的最少步数； 之后我们去推递推公式，首先我们先分析本题无法使用动态规划唯一困难为小猫可以跳过x再退回来，这样明显不符合动态规划的思想：后面的值去递推到前面，但是我们可以将其简化为两个步骤：

1. 向前走一步跳到dp[i]
2. 直接跳一倍的距离到达dp[i]

而步骤二又可以进一步细分为两个可能性：

1. i% 2 ==0 这时候跳到i可以通过直接从i/2跳过来
2. i%2 ==1 这时候我们可以在上一步时前进或后退之后调整位置调过来

求上面所有思路的最小步数，推到dp[input]则是解

题解

#include <iostream>
using namespace std;

int main()
{
    int input;
    cin >> input;
    if (input < 0){
        input = -input;
    }
    int dp[10000];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    dp[4] = 3;
    for (int i = 5; i<= input; i++){
        int mydouble;
        if(i % 2 == 1)
        {
            int double_plus1;
            int double_miner1;
            mydouble = min(dp[(i + 1) /2], dp[(i - 1) /2]) + 2;
        }else{
            mydouble = dp[i / 2] + 1;
        }
        int plus1 = dp[i - 1] + 1;
        dp[i] = min(plus1, mydouble);
    }
    cout << dp[input] << endl;
}