跳房子是小朋友玩的游戏。地面上画出一连串格子,每个格子里有一个整数,小朋友从外面跳入格子,并继续往前跳,直到跳出所有格子。每次跳跃的规则是,可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。请用c++求解
时间: 2024-05-29 10:11:34 浏览: 219
用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代码:
阅读全文