题解 | #不能连续吃草的牛II# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
        public int robRange(int[] nums, int start, int end) {
            if (start == end) {
                return nums[start];
            }
            int[] dp = new int[nums.length];
            dp[start] = nums[start];
            dp[start + 1] = Math.max(nums[start], nums[start + 1]);
            for (int i = start + 2; i <= end; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[end];
        }

        public int eatGrass(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            if (nums.length == 1) {
                return nums[0];
            }
            int res1 = robRange(nums, 0, nums.length - 2);
            int res2 = robRange(nums, 1, nums.length - 1);
            return Math.max(res1, res2);
        }
    }

编程语言是Java。

该题考察的知识点是动态规划

代码简短的文字解释如下：定义一个dp数组保存中间结果。初始化dp[start]为nums[start]，dp[start+1]为max(nums[start], nums[start+1])。然后从start+2开始遍历，dp[i]的值等于前两个状态的最大值加上当前位置的金额，即max(dp[i-2] + nums[i], dp[i-1])。返回dp[end]作为该范围内的最大抢劫金额。

然后在eatGrass函数中，先判断输入数组长度是否为0或1，如果是，则直接返回相应的值。然后分别计算从0到n-2和从1到n-1的两个范围内的最大抢劫金额，取其中较大的一个作为结果返回。