LeetCode 面试题 17.16. 按摩师

题目描述

标准解答 DP $O(n)$

01背包的思路，状态转移方程如下（dp[i][0/1]表示第i个预约选或不选得到的最长预约时间）

$dp[i][0] = max(dp[i-1][0], dp[i-1][1])$，即不选第i个预约的总时间为第i-1个预约选或不选的最大值

$dp[i][1] = dp[i-1][0] + nums[i]$，选第i个预约，则无法选择第i-1个

计算$dp[i][0/1]$时，只与前一个状态$dp[i-1][0/1]$有关，所以可以不用数组，而使用两个临时变量，通过状态转移计算，减小开销。（这个做法很巧妙）

class Solution {
public:
    int massage(vector<int>& nums) 
    {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        int dp0 = 0, dp1 = nums[0];

        for (auto i = 1; i < n; i++)
        {
            int tmpDp0 = max(dp0, dp1); // dp0: dp[i-1][0], dp1: dp[i-1][1]
            int tmpDp1 = dp0 + nums[i];

            dp0 = tmpDp0;   // dp0: dp[i][0], dp1: dp[i][1]
            dp1 = tmpDp1;
        }

        return max(dp0, dp1);
    }
};

网友的另一种dp思路

状态转移方程：

$dp[i] = max(dp[i-2]+nums[i], dp[i-1])$，$dp[i]$为从0到i总共能取到的最长预约时间

class Solution {
public:
    int massage(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0; 
        if(size == 1) return nums[0];

        vector<int> dp(size, 0);
        dp[0] = nums[0]; //dp[i] 表示nums[0...i] 能得到的最长时间
        dp[1] = max(nums[0],nums[1]);

        for(int i = 2; i < size; i++)
        {
            //遍历迄今为止的最大值，两种情况取较大：
            //1：预约本次，则上一次不预约（dp[i-2] + nums[i]）
            //2：本次不预约，则值为预约到上一次的最大值
            dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
        }

        return dp[size -1];
    }
};

个人解法1 递归 超时

起初发现的规律是，在第i个位置时，由于i+1不能选，考虑走i+2或i+3，两种走法取最大值，是一种比较暴力的做法，但最终超时了，因为重复计算的子问题太多了（比如go(0,num)算过一次go(0+3, num)，go(1,num)又要再算一遍go(1+2, num)）

class Solution {
public:
    int massage(vector<int>& nums) 
    {
        return max(go(0, nums), go(1, nums));
    }

    int go(int pos, vector<int>& num)
    {
        if (pos >= num.size()) 
        {
            return 0;
        }
        
        return num[pos] + max(go(pos + 2, num), go(pos + 3, num));
    }
};

个人解法2 从尾DP

这是顺从递归的思路进而产生的DP，感觉思维还是不太精炼，没有dp内味。

class Solution {
public:
    int massage(vector<int>& nums) 
    {
        
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        else if (n == 1)
        {
            return nums[0];
        }

        int m[n];
        for (auto i = n - 1; i >= 0; i--)
        {
            m[i] = nums[i];
            if (i + 3 >= n)
            {
                if (i + 2 < n)
                {
                    m[i] += m[i+2];
                }
            }
            else
            {
                m[i] += max(m[i+2], m[i+3]); 
            }
        }

        return max(m[0], m[1]);
    }
};

总结

• 选/不选的问题很容易归类到01背包类似的问题上去，没必要蛮力找规律再编码
• 边界问题考虑清楚

参考

官方题解