Leetcode 1262 -- 动态规划

题目描述

可被三整除的最大和

思路

本题
通用2
通用解法 $1$ 其实就是对针对本题代码修改之后的一个通用写法！

针对本题代码

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        int dp[n + 1][3];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 0;
        dp[0][1] = INT_MIN;
        dp[0][2] = INT_MIN;
        for(int i = 0; i < n; i ++ ) {
            int x = nums[i];
            if(x % 3 == 1) {
                dp[i + 1][0] = max(dp[i][2] + x, dp[i][0]);
                dp[i + 1][1] = max(dp[i][0] + x, dp[i][1]);
                dp[i + 1][2] = max(dp[i][1] + x, dp[i][2]);
            }
            else if(x % 3 == 2) {
                dp[i + 1][0] = max(dp[i][1] + x, dp[i][0]);
                dp[i + 1][1] = max(dp[i][2] + x, dp[i][1]);
                dp[i + 1][2] = max(dp[i][0] + x, dp[i][2]);
            }
            else { // x % 3 == 0
                dp[i + 1][0] = max(dp[i][0] + x, dp[i][0]);
                dp[i + 1][1] = max(dp[i][1] + x, dp[i][1]);
                dp[i + 1][2] = max(dp[i][2] + x, dp[i][2]);
            }
        }
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 0; j < 3; j ++ ) {
                cout << dp[i][j] << ' ';
            }
            cout << endl;
        }
        return dp[n][0];
    }
};

通用解法代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <time.h>

using namespace std;

int maxSumDivN1(const vector<int> &a, int k);
int maxSumDivN2(const vector<int> &a, int k);

const int N = 500, M = 500;
vector<int> arr(N);

int main()
{
    srand((unsigned int)time(NULL));
    for(int i = 0; i < N; i ++ )    
        arr[i] = rand() % M;
    for(int i = 2; i <= 100; i ++ ) {
        // cout << maxSumDivN1(a, i) << ' ' << maxSumDivN2(a, i) << endl;
        int a = maxSumDivN1(arr, i);
        int b = maxSumDivN2(arr, i);
        if(a != b) {
            cout << "Wrong: " << a << ' ' << b << endl;
        }
    }
    return 0;
}

int maxSumDivN1(const vector<int> &nums, int k) {
    vector<int> dp(k, INT_MIN);
    dp[0] = 0;
    for (int a : nums) {
        vector<int> dp2(k + 1, 0);
        for (int i = 0; i < k; ++i)
            dp2[(i + a) % k] = max(dp[(i + a) % k], dp[i] + a);
        dp = dp2;
    }
    return dp[0];
}

int maxSumDivN2(const vector<int> &nums, int k) {
    int n = nums.size();
    int dp[n + 1][k];
    memset(dp, -0x3f, sizeof dp);
    for(int i = 0; i < k; i ++ )    dp[0][i] = 0;
    bool flag[k];
    memset(flag, false, sizeof flag);   
    for(int i = 0; i < n; i ++ ) {
        for(int j = 0; j < k; j ++ ) {
            int sum = dp[i][j] + nums[i];
            int d = sum % k;
            flag[d] = true;
            dp[i + 1][d] = max(sum, max(dp[i + 1][d], dp[i][d]));
        }
        for(int j = 0; j < k; j ++ ) {
            if(flag[j]) flag[j] = false;
            else    dp[i + 1][j] = dp[i][j];
        }
    }
    return dp[n][0];
}