每日两题6

删除并获得点数

分析

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10001;
        // 预处理
        int arr[N] = {0};
        for (int& e : nums)
            arr[e] += e;
        
        // 在 arr 上进行 打家劫舍 问题
        vector<int> f(N), g(N);
        // 填表
        for(int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[N - 1], g[N - 1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

粉刷房子

分析：

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        const int N = costs.size() + 1;
        vector<int> dp0(N), dp1(N), dp2(N);

        for (int i = 1; i < N; i++) {
            dp0[i] = costs[i - 1][0] + min(dp1[i - 1], dp2[i - 1]);
            dp1[i] = costs[i - 1][1] + min(dp0[i - 1], dp2[i - 1]);
            dp2[i] = costs[i - 1][2] + min(dp1[i - 1], dp0[i - 1]);
        }
        return min(dp0[N - 1], min(dp1[N - 1], dp2[N - 1]));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        const int N = costs.size() + 1;
        vector<vector<int>> dp(N, vector<int>(3, 0));

        for (int i = 1; i < N; i++) {
            dp[i][0] = costs[i - 1][0] + min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = costs[i - 1][1] + min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = costs[i - 1][2] + min(dp[i - 1][1], dp[i - 1][0]);
        }
        return min(dp[N - 1][0], min(dp[N - 1][1], dp[N - 1][2]));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14