跳房子是小朋友玩的游戏。地面上画出一连串格子,每个格子里有一个整数,小朋友从外面跳入格子,并继续往前跳,直到跳出所有格子。每次跳跃的规则是,可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。
时间: 2024-06-06 13:08:02 浏览: 84
跳跳类的游戏
这是一个经典的动态规划问题。
设 $dp_i$ 表示从第 $i$ 个格子开始跳到最后一个格子的最小累加和,那么有以下的递推式:
$$
dp_i = \min\{dp_{i+1}, dp_{i+2}, dp_{i+3}\} + a_i
$$
其中 $a_i$ 表示第 $i$ 个格子里的整数。
边界条件为 $dp_n = a_n$,因为最后一个格子只能跳到自己。
最终答案为 $dp_1$。
可以使用自底向上的方式求解,时间复杂度为 $O(n)$。
阅读全文