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

本题是一个典型的动态规划问题，可以使用记忆化搜索的方法求解。

首先，定义一个二维数组dp[i][j]表示从第i个格子开始跳，跳到第j个格子的最小累加和。则dp[i][j]可以通过以下方式求得：

dp[i][j] = min{ dp[j][k] + sum[i][j] }，其中 i < k <= j，sum[i][j]表示从第i个格子跳到第j个格子的数的累加和。

因为每次跳跃只能跳到下一格、下下格或下下下格，所以可以预处理出从每个格子跳到下一个格子、下下个格子、下下下个格子的跳跃代价，即jump[0/1/2][i][j]表示从第i个格子跳到第j个格子的跳跃代价。然后，在求dp[i][j]时，枚举上一次跳跃到的格子k，计算出当前跳跃的代价dp[j][k] + jump[x][k][j]，并取最小值即可。

最后，dp[1][n]即为所求的答案。

以下是AC代码：

相关问题

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

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

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

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

这是一个比较经典的动态规划问题。可以使用记忆化搜索或者自底向上的动态规划求解。

记忆化搜索解法：

设 $dp(i)$ 表示从第 $i$ 个格子开始跳到最后一个格子所需的最小累加和。则有如下的状态转移方程：

$$
dp(i) = \min\{dp(i+1), dp(i+2), dp(i+3)\} + val(i)
$$

其中 $val(i)$ 表示第 $i$ 个格子里的整数。初始状态为 $dp(n+1) = 0$。

自底向上的动态规划解法：

设 $dp(i)$ 表示从第 $i$ 个格子开始跳到最后一个格子所需的最小累加和。则有如下的状态转移方程：

$$
dp(i) = \min\{dp(i+1), dp(i+2), dp(i+3)\} + val(i)
$$

其中 $val(i)$ 表示第 $i$ 个格子里的整数。初始状态为 $dp(n+1) = 0$。

可以从 $dp(n)$ 逆推回 $dp(1)$ 来获得最小累加和。