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

import java.util.*;


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

    
}

动态规划问题，关键还是动态规划方程及其初始值。难一点的动态规划跟递归一起考，比如找最长子数组的问题。所有的算法问题都是多个小技巧的组合，有的时候组合的太多开发人员脑内存有限，就会搞不出来