题解 | #牛群的夜间保卫II#

import java.util.*;


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

本题知识点分析：

1.动态规划

2.API函数Math.max

3.数组遍历

4.数学模拟

本题解题思路分析：

1.先根据values的长度，0,1,2分别返回

2.然后因为首尾是环形，因此要么是从第一个开始到n-2索引，要么是从第二个开始到n-1索引,然后取较大值就可以

3.其实就是遍历两次，分别去dp,然后求较大值

4.打家劫舍问题II

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~