The Massage Therapist Scheduling Problem

Problem link: https://leetcode.cn/problems/the-masseuse-lcci/

A renowned massage therapist receives a continuous stream of appointment requests. Each appointment can be accepted or declined. Due to the need for rest periods between sessions, she cannot accept consecutive appointments. Given a sequence of appointment durations, find the optimal set of appointments to maximize the total session time.

Example 1:

Input: [1,2,3,1]

Output: 4

Explanation: Selecting appointments 1 and 3 gives total time = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]

Output: 12

Explanation: Selecting appointments 1, 3, and 5 gives total time = 2 + 9 + 1 = 12.

Approach

1. State Definition: We use two arrays to track our states:
• take[i]: Maximum time up to position i when appointment i is selected
• skip[i]: Maximum time up to position i when appointment i is not selected
2. State Transition:
• take[i] = skip[i-1] + nums[i] (if we take appointment i, we must have skipped i-1)
• skip[i] = max(take[i-1], skip[i-1]) (if we skip i, we can either have taken or skipped i-1)
3. Initialization: take[0] = nums[0], skip[0] = 0
4. Processing Order: Fill both arrays from left to right
5. Result: max(take[n-1], skip[n-1])

Code Implementation

class AppointmentScheduler {
public:
    int maxAppointmentTime(vector<int>& appointments) {
        int n = appointments.size();
        if(n == 0) return 0;
        
        vector<int> take(n);
        vector<int> skip(n);
        take[0] = appointments[0];
        
        for(int i = 1; i < n; i++) {
            take[i] = skip[i-1] + appointments[i];
            skip[i] = max(take[i-1], skip[i-1]);
        }
        
        return max(take[n-1], skip[n-1]);
    }
};

House Robber II

Problem link: https://leetcode.cn/problems/house-robber-ii/

You are a professional thief planning to rob houses arranged in a circle. Each house contains a certain amount of cash. The first and last houses are neighbors, and adjacent houses have security systems that will trigger an alarm if two adjacent houses are robbed on the same night.

Given a non-negative integer array representing the amount of money in each house, compute the maximum amount you can rob without triggering the alarm.

Example 1:

Input: nums = [2,3,2]

Output: 3

Explanation: You cannot rob house 1 (amount = 2) and house 3 (amount = 2) because they are adjacent.

Example 2:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (amount = 1) and house 3 (amount = 3). Total amount = 1 + 3 = 4.

Approach

The circular arrangement creates a dependency between the first and last houses. We can solve this by breaking it into two linear problems:

1. Case 1: Rob the first house (cannot rob the last house)
2. Case 2: Skip the first house (can rob the last house)

The solution is the maximum value from these two cases.

Code Implementation

class HouseRobber {
public:
    int rob(vector<int>& wealth) {
        int n = wealth.size();
        if(n == 0) return 0;
        if(n == 1) return wealth[0];
        
        // Case 1: Rob first house, skip last
        int case1 = linearRob(wealth, 0, n-2);
        // Case 2: Skip first house, can rob last
        int case2 = linearRob(wealth, 1, n-1);
        
        return max(case1, case2);
    }
    
private:
    int linearRob(vector<int>& wealth, int start, int end) {
        if(start > end) return 0;
        
        int take = wealth[start];
        int skip = 0;
        
        for(int i = start+1; i <= end; i++) {
            int newTake = skip + wealth[i];
            int newSkip = max(take, skip);
            take = newTake;
            skip = newSkip;
        }
        
        return max(take, skip);
    }
};

Delete and Earn

Problem link: https://leetcode.cn/problems/delete-and-earn/

You are given an integer array nums. You can perform operations where you delete any element nums[i] and earn nums[i] points. After deletion, you must delete all elements equal to nums[i]-1 and nums[i]+1.

Starting with 0 points, return the maximum points you can earn through these operations.

Example 1:

Input: nums = [3,4,2]

Output: 6

Explanation: Delete 4 to earn 4 points, which forces deletion of 3. Then delete 2 to earn 2 points. Total points = 4 + 2 = 6.

Example 2:

Input: nums = [2,2,3,3,3,4]

Output: 9

Explanation: Delete all 3s to earn 9 points, which forces deletion of 2s and 4. Total points = 3 + 3 + 3 = 9.

Approach

This problem is a variation of the House Robber problem. The key insight is to transform the problem into a House Robber scenario by:

1. Creating a frequency array where each index represents a number and the value at that index represents the total points for that number
2. Applying the House Robber DP approach to this array to select non-adjacent numbers for maximum points

Code Implementation

class PointEarner {
public:
    int maxPoints(vector<int>& numbers) {
        int maxValue = 0;
        for(int num : numbers) {
            maxValue = max(maxValue, num);
        }
        
        vector<int> points(maxValue + 1, 0);
        for(int num : numbers) {
            points[num] += num;
        }
        
        // Now apply House Robber approach to points array
        int take = points[0];
        int skip = 0;
        
        for(int i = 1; i <= maxValue; i++) {
            int newTake = skip + points[i];
            int newSkip = max(take, skip);
            take = newTake;
            skip = newSkip;
        }
        
        return max(take, skip);
    }
};

Paint House

Problem link: https://leetcode.cn/problems/JEj789/

There are n houses in a row, each of which can be painted red, blue, or green. You must paint all houses such that no two adjacent houses have the same color. The cost of painting each house with different colors is given by an n x 3 matrix costs, where costs[i][j] represents the cost of painting house i with color j.

Calculate the minimum cost to paint all houses.

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]

Output: 10

Explanation: Paint house 0 blue, house 1 green, and house 2 blue. Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]

Output: 2

Approach

1. State Definition: We use a DP table with three states for each position:
• dp[i][0]: Minimum cost up to house i when house i is painted red
• dp[i][1]: Minimum cost up to house i when house i is painted blue
• dp[i][2]: Minimum cost up to house i when house i is painted green
2. State Transition:
• dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]
• dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]
• dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]
3. Initialization: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]
4. Processing Order: Fill the table from left to right
5. Result: min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]))

Code Implementation

class HousePainter {
public:
    int minPaintingCost(vector& costs) {
        int n = costs.size();
        if(n == 0) return 0;
        
        vector dp(n, vector<int>(3, 0));
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        
        for(int i = 1; i < n; i++) {
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0];
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1];
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
        }
        
        return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]));
    }
};