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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
      public int eatGrass (int[] nums) {
        // write code here
        if(nums.length==0){
            return 0;
        }else if(nums.length==1){
            return nums[0];
        }else if(nums.length==2){
            return nums[1];
        }
        return Math.max(dp(Arrays.copyOfRange(nums,0,nums.length-1)),dp(Arrays.copyOfRange(nums,1,nums.length)));
    }

    public int dp(int[] nums){
        if(nums.length==0){
            return 0;
        }else if(nums.length==1){
            return nums[0];
        }else if(nums.length==2){
            return nums[1];
        }
        int[] arr = new int[nums.length];
        arr[0] = nums[0];
        arr[1] = Math.max(nums[1],nums[0]);
      
        int value = Math.max(arr[0],Math.max(arr[1],arr[2]));
        for(int i=2;i<nums.length;i++){
            arr[i] = Math.max(arr[i-2]+nums[i],arr[i-1]);
            value = Math.max(value,arr[i]);
        }
        return value;
    }
}

本题考察的知识点是动态规划，所用编程语言是java。

本题相比与前一题的难点在于数组头部和数组尾部相邻，所以我们需要考虑两种情况

1.考虑数组头部元素，那么数组尾部元素不应该考虑在内

2.不考虑数组头部元素，那么数组尾部元素应该考虑在内