『LeetCode|每日一题』----＞按摩师

目录

1.每日一句

2.作者简介

『LeetCode|每日一题』按摩师

1.每日一题

2.解题思路

        2.1 思路分析（动态规划）

        2.2 核心代码（dp） 

        2.3 完整代码

        2.4 运行结果

        2.5 更简易的方法

---

1.每日一句

万事皆可期，欢愉且胜意

2.作者简介

🏡个人主页：XiaoXiaoChen-2716 

📚学习专栏：力扣专栏

🕒发布日期：2022/11/14

『LeetCode|每日一题』按摩师

1.每日一题

原文链接--->点我

2.解题思路

        2.1 思路分析（动态规划）

看到这题我就想到了打家劫舍那一题，也是类似的方法，动态规划，都是求最大

打家劫舍

        S1：首先是特殊情况分析，空数组和数组长度为1两种情况，空数组直接返回0即可，数组长度为1就返回nums[0]即可；

        S2：动态规划定义一个dp数组，首先因为题目只能选择相邻的，所以第0位置和第1位置都要先初始化，第0位置就等于nums[0]，这个很好理解，那么第一位置呢？可以这么想，如果数组长度为2，那么肯定是返回其中大的那一个，此时读者肯定能够知道第1位置等于多少了；

        S3：然后是递推关系式，第i个元素的最长时间，它无非就是两种情况，第一种就是跟它间隔一个的dp[i - 2]然后加上自己本身的时间nums[i]（这种情况就是不接受第i - 1的预约），第二种情况就是它的相邻位置dp[i - 1]，在这两者之间取最大的那个即可（这种就是接受第i - 1的预约）；

        S4：最后返回nums[len - 1]即可

        2.2 核心代码（dp） 

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0] , nums[1]);
        for(int i = 2 ; i < len ; i++){
            dp[i] = Math.max(nums[i] + dp[i - 2] , dp[i - 1]);
        }

        2.3 完整代码

class Solution {
    public int massage(int[] nums) {
        int len = nums.length;
        if(len <= 0){
            return 0;
        }else if(len == 1){
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0] , nums[1]);
        for(int i = 2 ; i < len ; i++){
            dp[i] = Math.max(nums[i] + dp[i - 2] , dp[i - 1]);
        }
        return dp[len - 1];
    }
}

        2.4 运行结果

        2.5 更简易的方法

其实理解了题目的读者可以发现，用一个dp数组来存储最长预约时间，其实每次都只用到了两个元素，所以我们可以定义一个one和two，就不需要dp数组了，这样节约了空间，只需要三步，第一步定义一个flag存储当前two的值，然后two就是取two和one + nums[i]中的最大值，最后把flag存储的值赋值给one就相当于往后移了，思想和dp数组是一样的  

class Solution {
    public int massage(int[] nums) {
        int one = 0;
        int two = 0;
        for(int i = 0 ; i < nums.length ; i++){
            int flag = two;
            two = Math.max(two , one + nums[i]);
            one = flag;
        }
        return two;
    }
}

🍁 类似题目推荐：

1.数据结构基础

2.算法专项练习

3.剑指offer专项练习

4.推荐一个学习网站：LeetCode，算法的提升在于日积月累，只有每天练习才能保持良好的状态

如果文章对各位大佬有帮助就支持一下噢，不好的地方请各位大佬多多指教！