链接：https://ac.nowcoder.com/acm/contest/58069/B 来源：牛客网 现在要入冬了，小熊要赶紧出去觅食，那样的话它才能在冬眠前补充足够的能量。小熊是一只聪明的熊，为了节省时间，它早早就记住了哪里有食物，注意这里是一个数轴，小熊的树洞在原点 0 0 的位置上，食物在 � x 的位置上。特别的是，小熊走每一步都有三种选择，可以选择步长为 1 1、 2 2、 3 3 中的一种。现在小熊从树洞出发，它想在出发前就能够知道自己拿到食物最少需要走多少步，以便它能够做好相应的准备，你能帮帮它吗

这是一道动态规划的题目。我们可以从小熊的位置 0 出发，每次向右移动 1、2 或 3 步，直到到达目标位置 x。设 dp[i] 表示小熊从位置 i 出发到达目标位置 x 的最少步数，则有转移方程：

dp[i] = min(dp[i+1], dp[i+2], dp[i+3]) + 1

边界条件为 dp[x] = 0，因为小熊已经到达目标位置。

最终答案为 dp[0]，即从位置 0 出发到达目标位置 x 的最少步数。

代码实现如下：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 5;

int dp[MAXN];

int main() {
    int x;
    cin >> x;

    memset(dp, 0x3f, sizeof(dp));
    dp[x] = 0;

    for (int i = x - 1; i >= 0; i--) {
        dp[i] = min(dp[i+1], min(dp[i+2], dp[i+3])) + 1;
    }

    cout << dp[0] << endl;

    return 0;
}