跳房子是小朋友玩的游戏。地面上画出一连串格子，每个格子里有一个整数，小朋友从外面跳入格子，并继续往前跳，直到跳出所有格子。每次跳跃的规则是，可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。 输入格式: 第一行输入格子数 n (1<n<100)，第二行输入从起点处到终点处每个格子里的数，该数小于10。 输出格式: 输出最小累加和。 输入样例: 在这里给出一组输入。例如： 4 3 3 2 5 输出样例: 在这里给出相应的输出。例如： 2使用C++实现

好的，下面是C++代码实现，仅供参考：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int nums[N];
int dp[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> nums[i];

    dp[n] = nums[n];
    dp[n - 1] = nums[n - 1] + nums[n];
    dp[n - 2] = nums[n - 2] + nums[n - 1] + nums[n];
    for (int i = n - 3; i >= 0; i -- )
        dp[i] = min(dp[i + 1], min(dp[i + 2], dp[i + 3])) + nums[i];

    cout << dp[0] << endl;

    return 0;
}

具体实现和算法思路已经在前面介绍过了，这里就不再赘述了。

相关问题

跳房子是小朋友玩的游戏。地面上画出一连串格子，每个格子里有一个整数，小朋友从外面跳入格子，并继续往前跳，直到跳出所有格子。每次跳跃的规则是，可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。

这是一个经典的动态规划问题，可以用递归和记忆化搜索或者动态规划两种方法求解。

1. 递归和记忆化搜索方法：

定义一个函数 f(i) 表示从第 i 个格子开始跳到最后一个格子的最小累加和，那么有：

f(i) = min{f(i+1), f(i+2), f(i+3)} + a[i]

其中 a[i] 表示第 i 个格子里的数。注意需要添加边界条件，即当跳到最后一个格子时，返回 0。

使用记忆化搜索方法，可以将每次递归过程中计算的 f(i) 存储下来，避免重复计算。

2. 动态规划方法：

同样定义状态 f(i) 表示从第 i 个格子开始跳到最后一个格子的最小累加和，那么有：

f(i) = min{f(i+1), f(i+2), f(i+3)} + a[i]

其中 a[i] 表示第 i 个格子里的数。需要注意的是，由于状态 f(i) 只依赖于 f(i+1), f(i+2), f(i+3) 这三个状态，因此可以使用滚动数组的方式来优化空间复杂度，将数组长度降为常数级别。

最终答案即为 f(1)。

小明和朋友玩跳格子的游戏,有 n 个连续格子,每个格子有不同的分数,小朋友可以选择

小明和朋友玩跳格子游戏是一个有趣的活动。游戏中，有n个连续的格子，每个格子都有不同的分数。小朋友可以选择从任意一个格子开始跳，跳到下一个格子可以获得该格子的分数，并且可以选择继续跳向下一个格子或者停下来。游戏的目标是获得最高的总分。

在游戏开始之前，小明和朋友会仔细观察每个格子的分数，以便做出最佳的决策。他们会考虑每个格子的分数以及与其他格子的关系，比如相邻格子的分数差距，以及是否有连续高分或低分的情况。他们会根据这些信息来制定策略。

在游戏过程中，小明和朋友会根据制定的策略来选择跳向的下一个格子。他们可能会优先选择分数高的格子，因为这样能够累积更多的总分。但是他们也会考虑到分数差距，如果存在一个低分和高分之间的连续格子，他们可能会选择跳过这段连续格子，以避免得到较低的总分。

跳格子游戏不仅仅考验玩家的决策能力，还锻炼了他们的观察力和分析能力。他们需要快速判断每个格子的潜在价值，并做出准确的决策。这个游戏不仅能够增加玩家的计算能力，还能够培养他们的策略思维和灵活性。

总之，小明和朋友玩跳格子游戏通过选择不同的格子来累积分数，这个具有挑战性和思考的活动，可以让玩家在娱乐中提升自己的思维能力。