leetcode：那些年我遇到过的编程题010：按摩师

leetcode：那些年我遇到过的编程题010：按摩师审完题目，大概就是让我们在一个数组中找出来互不相临的数相加的最大值。虽然想到了用动态规划，但是最后代码怎么都写不出来…

class Solution {
    int max = 0
    public int massage(int[] nums) {
        Set<Integer> list = new HashSet<>(nums.length);
        for{int i = 0;i<nums.length;i++}{
            if(!list.contains(i-1)&&!list.contains(i+1)){
                list.add[i];
                max+=nums[i];
            }
        }
        if(i<nums.length){
            Select(i);
        }
    }
    public void Select(i){
        
    }
}

看了答案之后又仔细想了想再动键盘

class Solution {
    public int massage(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1){return nums[0];}
        int sdp0 = 0,sdp1= nums[0];
        for(int i =1;i<n;i++){
            int dp0 = Math.max(sdp0,sdp1);
            int dp1 = sdp0 + nums[i];
            sdp0 = dp0;
            sdp1 = dp1;
        }
        return Math.max(sdp0,sdp1);
    }
}

总结一下，动态规划主要就是要弄清楚现在的状态和上一个状态之间的关系，分出几种情况来讨论，再写代码，思路会清晰很多。