长大后想做什么？做回小孩！

0%

程序员面试金典——按摩师

发表于 分类于 Valine：
本文字数： 341

##NO.17.16 按摩师 简单

8Hog8U.png

思路一：动态规划

dp数组的含义：dp[i]表示[0,i]区间内的最优预约集合。

初始化：dp[0]只能是nums[0]，dp[1]只有两个请求的时候nums[0]和nums[1]一定是相邻的，所以只能选择较大的一个。

状态转移：dp[i]=Max(dp[i-1],dp[i-2]+nums[i])，如果选择了包含nums[i-1]的预约序列那么nums[i]就不能选因为二者相邻，反之可以将nums[i]加入到预约序列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int massage(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    if (nums.length==1)return nums[0];
    int[] dp=new int[nums.length];
    //初始化
    dp[0]=nums[0];
    dp[1]=Math.max(nums[0],nums[1]);
    //状态转移
    for (int i = 2; i < nums.length; i++) {
        dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
    }
    return dp[nums.length-1];
}

时间复杂度：O(n)

空间复杂度：O(n)

只需要用两个记录dp[i-1]和dp[i-2]的值就可以了，可以将时间复杂度降低到O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int massage(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    if (nums.length==1)return nums[0];
    //记录前一个dp值和前前一个dp值
    int prepredp=0,predp=0;
    //状态转移
    for (int i = 0; i < nums.length; i++) {
        int currdp=Math.max(predp,prepredp+nums[i]);
        prepredp=predp;
        predp=currdp;
    }
    return predp;
}

时间复杂度：O(n)

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github