[dynamic planning medium] leetcode 198. looting 740. delete and get points

LeetCode 198. raid homes and plunder houses

https://leetcode.cn/problems/house-robber
You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm , The maximum amount that can be stolen overnight .

Input ：[1,2,3,1]
Output ：4
explain ： Steal 1 House No ( amount of money = 1) , And then steal 3 House No ( amount of money = 3).
Maximum amount stolen = 1 + 3 = 4 .

Input ：[2,7,9,3,1]
Output ：12
explain ： Steal 1 House No ( amount of money = 2), Steal 3 House No ( amount of money = 9), Then steal 5 House No ( amount of money = 1).
Maximum amount stolen = 2 + 9 + 1 = 12 .

Add ： From 1 House No. 1 starts looting or no 2 It's OK to start looting House No .

1. Design status

dp[i] Express 0~i The maximum amount of money you can get after home robbery .

2. Write the equation of state transition

If robbery i-1 No. 1 house, then you can't rob any more i House No , Only one house can be robbed , So the state transfer equation is ：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

3. Set the initial state

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

4. Perform state transition

5. Return to the final solution

dp[numsSize - 1]

Solution

int max(int a, int b) {
    
    return a > b ? a : b;
}

int rob(int* nums, int numsSize){
    
    if (numsSize == 1) {
    
        return nums[0];
    }

    int dp[101];
    //  The initial state 
    dp[0] = nums[0];
    dp[1] = max(nums[1], nums[0]);
 

    for(int i = 2; i < numsSize; ++i) {
    
        //  State shift 
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    //  Return to the final solution 
    return dp[numsSize-1];
}

( Expand )LeetCode 740. Delete and get points

https://leetcode.cn/problems/delete-and-earn/
Give you an array of integers nums , You can do something with it .

In every operation , Choose any one nums[i] , Delete it and get nums[i] Number of points . after , You have to delete it all be equal to nums[i] - 1 and nums[i] + 1 The elements of .

At first you have 0 Points . Return the maximum number of points you can get through these operations .

Input ：nums = [2,2,3,3,3,4]
Output ：9

int max(int a, int b) {
    
    return a > b ? a : b;
}
//  Home robbing code 
int rob(int* nums, int numsSize){
    
    if (numsSize == 1) {
    
        return nums[0];
    }

    int dp[numsSize];
    dp[0] = nums[0];
    dp[1] = max(nums[1], nums[0]);
 

    for(int i = 2; i < numsSize; ++i) {
    
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    return dp[numsSize-1];
}

int deleteAndEarn(int* nums, int numsSize){
    
    // nums = [2,2,3,3,3,4]
    //  take  nums  Array mapping  sum = [0,0,2,3,1], sum[i]  Express  nums  in  i  The number of 
    //  use  val  The array records the sum of the same elements  val = [0,0,4,9,4] ==>  It turns into the problem of robbing families 
    int sum[10001];
    int val[10001];
    memset(sum, 0, sizeof(sum));
    for (int i = 0; i < numsSize; ++i) {
    
        sum[nums[i]]++;
    }
    for (int i = 0; i < 10001; ++i) {
    
        val[i] = i * sum[i];
    }
    //  Directly call the code of home robbing 
    return rob(val, 10001);
}