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

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

记忆化搜索解法：

设 $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)$ 来获得最小累加和。