文章目录

题目

代码展示

---

题目

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/the-masseuse-lcci
 

代码展示

简而言之，就是求最大 子序和，条件是element不能是连续的
思路：递归 + 记忆
练习点：如何判断key是否出现在HashMap中？如何将kv写入到HashMap中？
遗留问题：函数调用函数的时候，是否需要self、this？java如何给形参设置默认值？

import java.util.HashMap;

public class Solution {
    private HashMap back = new HashMap<>();
    int numLen;

    private int maxCount(int[] times, int index){
        if(index >= numLen)
            return 0;
        if(index + 1 == numLen)
            return times[index];
        if (index + 2 == numLen)
            return Math.max(times[index], times[index+1]);

        int res2, res3;

        if (back.containsKey(index+2))
            res2 = back.get(index+2);
        else{
            res2 = maxCount(times, index+2);
            back.put(index+2, res2);
        }

        if (back.containsKey(index+3))
            res3 = back.get(index+3);
        else{
            res3 = maxCount(times, index+3);
            back.put(index+3, res3);
        }

        return Math.max(times[index] + res2, times[index+1]+res3);

    }

    public int massage(int[] nums) {
        numLen = nums.length;
        return maxCount(nums, 0);
    }
}

class Solution:
    def __init__(self):
        self.back = dict()

    def maxCount(self, times, index=0):
        if len(times[index:]) <= 0: return 0
        if len(times[index:]) == 1: return times[index]
        if len(times[index:]) == 2: return max(times[index:])

        if index + 2 not in self.back:
            res2 = self.maxCount(times, index+2)
            self.back[index+2] = res2
        else:
            res2 = self.back[index+2]

        if index + 3 not in self.back:
            res3 = self.maxCount(times, index+3)
            self.back[index+3] = res3
        else:
            res3 = self.back[index+3]

        return max(times[index] + res2, times[index+1] + res3)

    def massage(self, nums: List[int]) -> int:
        return self.maxCount(nums)