题解 | #牛牛的跳跃挑战#

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的障碍物开始跳跃而这是边界条件