题解 | #牛牛的跳跃挑战#
牛牛的跳跃挑战
https://www.nowcoder.com/practice/0c99c2161c2d4a4e91ca55363cc0e059
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param height int整型一维数组 * @return int整型 */ public int minEnergyJump (int[] height) { // write code here if (height.length == 0) { return 0; } else if (height.length == 1) { return height[0]; } else if (height.length == 2) { return Math.min(height[0], height[1]); } else if (height.length == 3) { return Math.min(Math.min(height[0], height[1]), height[2]); } int[] arr = new int[height.length]; int min_power = Integer.MAX_VALUE; for (int i = 3; i < height.length; i++) { arr[i] = Math.min(Math.min(arr[i - 1] + height[i - 1], arr[i - 2] + height[i - 2]), arr[i - 3] + height[i-3]); } return Math.min(Math.min(arr[arr.length - 1] + height[arr.length - 1], arr[arr.length - 2] + height[arr.length - 2]), arr[arr.length - 3] + height[arr.length-3]); } }
本题考察的是动态规划,所用的编程语言是java。
我们关于动态规划只要明确两点,第一点状态转移方程 第二点边界条件
状态转移方程对于此题再简单不过了,题目说牛牛可以选择跳过一个或两个或三个障碍物,这便是状态转移方程
动物牛可以选择从下标为 0 或下标为 1 或者下标2的障碍物开始跳跃而这是边界条件