跳房子是小朋友玩的游戏。地面上画出一连串格子,每个格子里有一个整数,小朋友从外面跳入格子,并继续往前跳,直到跳出所有格子。每次跳跃的规则是,可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。 输入格式: 第一行输入格子数 n (1<n<100),第二行输入从起点处到终点处每个格子里的数,该数小于10。 输出格式: 输出最小累加和。 输入样例: 在这里给出一组输入。例如: 4 3 3 2 5 输出样例: 在这里给出相应的输出。例如: 2
时间: 2024-02-26 07:52:56 浏览: 21
这道题可以使用动态规划算法求解,具体思路如下:
定义一个一维数组dp,其中dp[i]表示从第i个格子开始一直跳到终点的最小累加和。
状态转移方程为:dp[i] = min(dp[i+1], dp[i+2], dp[i+3]) + nums[i],其中nums[i]表示第i个格子里的数。
解释一下这个方程,dp[i]表示从第i个格子开始跳到终点的最小累加和,可以从i+1、i+2、i+3这三个格子中的任意一个跳过来,取其中的最小值再加上当前格子里的数nums[i]即可。
最终的答案就是dp[0],因为从起点开始跳到终点即相当于从0开始跳到终点。
具体实现时,可以从终点开始倒序遍历数组,计算dp值即可。
Python代码实现如下:
相关问题
跳房子是小朋友玩的游戏。地面上画出一连串格子,每个格子里有一个整数,小朋友从外面跳入格子,并继续往前跳,直到跳出所有格子。每次跳跃的规则是,可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。
这是一个经典的动态规划问题,可以用递归和记忆化搜索或者动态规划两种方法求解。
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)$ 来获得最小累加和。