算法动态规划

同余类分解状态优化DP

字数统计: 1.9k字   |   阅读时长: 8分
, , , ,

摘要: 同余类分解状态优化DP

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文通过两个力扣的题目看一下通过同余类分解状态的方式优化 DP。此外这两个问题都另外有贪心和自动机的解法。

同余类分解状态

动态规划中的状态有时可以按模某个数 $a$ 的同余类进行分解：模 $a$ 余 0 的归一类，模 $a$ 余 1 的归一类，…, 模 $a$ 余 $a-1$ 的归一类。这样就将要推导的状态 0 <= i < n 分为了 $a$ 类。

计算状态 dp[i] 时，转移方程的形式类似于 dp[i] = f(dp[i + k * a])，即状态只会在同一个同余类中转移。

题目

1262. 可被三整除的最大和

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

提示：

1
2
1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

示例 1：
输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：
输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：
输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

算法1：贪心

数组和为 sum：

  • 若 sum % 3 == 0 返回sum。
  • 若 sum % 3 == 1 sum 减去模3余1的数中最小的1个，或者减去模3余2中最小的2个。
  • 若 sum % 3 == 2 sum 减去模3余2的数中最小的1个，或者减去模3余1中最小的2个。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        const int MAXX = 4e4 + 1;
        if(nums.empty()) return 0;
        int min1 = MAXX, sub_min1 = MAXX, min2 = MAXX, sub_min2 = MAXX;
        int sum = 0;
        for(int num: nums)
        {
            sum += num;
            if(num % 3 == 1)
            {
                if(num < min1)
                {
                    sub_min1 = min1;
                    min1 = num;
                }
                else if(num < sub_min1)
                    sub_min1 = num;
            }
            else if(num % 3 == 2)
            {
                if(num < min2)
                {
                    sub_min2 = min2;
                    min2 = num;
                }
                else if(num < sub_min2)
                    sub_min2 = num;
            }
        }
        int ans = sum;
        if(sum % 3 == 1)
        {
            if(min1 < MAXX)
                ans = sum - min1;
            if(sub_min2 < MAXX)
                ans = max(ans, sum - min2 - sub_min2);
        }
        if(sum % 3 == 2)
        {
            if(min2 < MAXX)
                ans = sum - min2;
            if(sub_min1 < MAXX)
                ans = max(ans, sum - min1 - sub_min1);
        }
        return ans;
    }
};

算法2：动态规划

1
2
3
4
5
6
7
8
9
10
状态定义
dp[i][j] := [0..i-1] 上取出若干数的最大和，且和模 3 余 j

初始化
dp[0][1] = dp[0][2] = INT_MIN;
dp[0][0] = 0; 

状态转移
dp[i][j] = max(dp[i - 1][j]
            dp[i - 1][(j - (nums[i] % 3) + 3) % 3] + nums[i])

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(3));
        dp[0][0] = 0; dp[0][1] = dp[0][2] = INT_MIN;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for(int j = 0; j < 3; ++j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - (x % 3) + 3) % 3]);
        }
        return dp[n][0];
    }
};

算法3：有限自动机

有限自动机使用非常广泛: 例如正则表达式的引擎，编译器的词法和语法分析，网络协议等。

记 DFA $M = (S, \Sigma, f, S_{0}, F)$

首先看状态集合 $S$：

  • 0: 和模 3 余 0
  • 1: 和模 3 余 1
  • 2: 和模 3 余 2

再看字母表 $\Sigma$ : 正整数。

初始状态 $S_{0} = 0$。

终结状态 $F = \{0\}$。

三个状态各有一个字段记录额外信息：当前的和的最大值。

读取 nums 直至读完，对每个数字，更新 3 个状态的记录信息的字段。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
vector<int> state({0, INT_MIN, INT_MIN});
for(int num: nums)
{
    vector<int> nxt(3);
    for(int s = 0; s <= 2; ++s)
    {
        nxt[(s + num) % 3] = max(state[(s + num) % 3], state[s] + n);
    }
    state = nxt;
}

1363. 形成三的最大倍数

给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。

如果无法得到答案，请返回一个空字符串。

提示：

1
2
3
1 <= digits.length <= 10^4
0 <= digits[i] <= 9
返回的结果不应包含不必要的前导零。

示例 1：
输入：digits = [8,1,9]
输出：”981”

示例 2：
输入：digits = [8,6,7,1,0]
输出：”8760”

示例 3：
输入：digits = [1]
输出：””

示例 4：
输入：digits = [0,0,0,0,0,0]
输出：”0”

算法1：贪心

一个数能被 3 整除，当且仅当它的各位数字之和能被 3 整除。

首先求出数组各元素之和 S。

  • 若 S 是 3 的倍数，那么选择数组 digits 中的所有元素，它们任意组成的数都能被 3 整除，因此我们只需要将其从大到小排序再连接成一个数即可；
  • 若 S 模 3 余 1，我们从 digits 中删除一个最小的模 3 余 1 的数，如果没有这样的数，就删除两个最小的模 3 余 2 的数；
  • 若 S 模 3 余 2，与上面的情况类似，我们从 digits 中删除一个最小的模 3 余 2 的数，如果没有这样的数，就删除两个最小的模 3 余 1 的数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        vector<int> cnts(10);
        int sum = 0;
        for(int i: digits)
        {
            sum += i;
            ++cnts[i];
        }
        if(sum % 3 == 1)
        {
            bool flag = false;
            for(int i = 1; i <= 9; i += 3)
            {
                if(cnts[i] > 0)
                {
                    flag = true;
                    --cnts[i];
                    break;
                }
            }
            if(!flag)
            {
                int cnt = 2;
                int i = 2;
                while(i <= 9)
                {
                    if(cnts[i] > 0)
                    {
                        --cnts[i];
                        --cnt;
                    }
                    else
                        i += 3;
                    if(cnt == 0)
                    {
                        flag = true;
                        break;
                    }
                }
            }
            if(!flag)
                return "";
        }
        else if(sum % 3 == 2)
        {
            bool flag = false;
            for(int i = 2; i <= 9; i += 3)
            {
                if(cnts[i] > 0)
                {
                    flag = true;
                    --cnts[i];
                    break;
                }
            }
            if(!flag)
            {
                int cnt = 2;
                int i = 1;
                while(i <= 9)
                {
                    if(cnts[i] > 0)
                    {
                        --cnts[i];
                        --cnt;
                    }
                    else
                        i += 3;
                    if(cnt == 0)
                    {
                        flag = true;
                        break;
                    }
                }
            }
            if(!flag)
                return "";
        }
        string result;
        for(int i = 9; i >= 0; --i)
        {
            if(i == 0 && result.empty())
            {
                if(cnts[0] == 0)
                    return "";
                else
                    return "0";
            }
            result += string(cnts[i], '0' + i);
        }
        return result;
    }
};

算法2：动态规划

1
2
3
4
5
6
7
8
dp[i][j] := [0..i-1] 上取出若干数的最大数量，且和模 3 余 j
初始化
dp[0][0] = 0; 
dp[0][1] = dp[0][2] = INT_MIN;

转移
dp[i][j] = max(dp[i - 1][j]
            dp[i - 1][(j - (nums[i] % 3) + 3) % 3] + 1)

推完 dp 后用 dp 的信息贪心构造答案。这个贪心是在 dp 前的排序做的。见代码。

排序那里用桶排序的话可以降低时间复杂度。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        int n = digits.size();
        sort(digits.begin(), digits.end());
        vector<vector<int>> dp(n + 1, vector<int>(3, 0));
        for(int j = 1; j < 3; ++j)
            dp[0][j] = INT_MIN;
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < 3; ++j)
                dp[i][j] = max(dp[i - 1][j], 1 + dp[i - 1][((j - (digits[i - 1] % 3)) + 3) % 3]);
        if(dp[n][0] < 0)
            return "";

        string result;
        int j = 0;
        for(int i = n; i >= 1; --i)
        {
            if(dp[i][j] == 1 + dp[i - 1][(j - (digits[i - 1] % 3) + 3) % 3])
            {
                // 选了 digits[i]
                result += to_string(digits[i - 1]);
                j = (j - (digits[i - 1] % 3) + 3) % 3;
                if(result == "0")
                    return "0";
            }
        }
        return result;
    }
};
Share