leetcode---面试题 17.16. 按摩师

这道题其实和 leetcode—198.打家劫舍是一样的，典型的dp问题，dp[i]表示在第 i 个请求到来后的总预约时间。我们对于第 i 个预约请求有两种选择(接和不接)，接的话则表示他是从第 i-2 个请求过来的(因为不能接相邻的请求)，不接的话其总预约时间不变(和dp[i-1]相同)。所以状态转移方程为 $dp(i)=max(dp(i-1),dp(i-2)+num(i))$

int massage(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    else if(n == 1)
        return nums[0];
    int dp[1000000]={0};
    dp[0] = nums[0];
    dp[1] = max(nums[1],dp[0]);
    for(int i = 2;i < n;i++)
    {
        dp[i] = max(dp[i-1],dp[i-2] + nums[i]);
    }
    return dp[n-1];
}

以上代码我们可以在空间上优化，我们每次只关心 $dp[i-1],dp[i-2],dp[i]$

int massage(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    else if(n == 1)
        return nums[0];
    int a = nums[0];
    int b = max(nums[1],a);
    int c = b;
    for(int i = 2;i < n;i++)
    {
        c = max(b,a + nums[i]);
        a = b;
        b = c;
    }
    return c;
}

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_39781096/article/details/105071899
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-04-19 17:23:54
阅读 ( 1656 )
分类：面试题

leetcode---面试题 17.16. 按摩师

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看