题目描述
思路解析动画文字版
只记和对 3 的余数这一个特征,三种余数三个格子。新数余数为 r 时,要凑出余 j 就接到上一行余 (j 减 r) 的那一格,取「不要它」和「接上它」的较大者。
总览 · 三列对应三种余数：这是一张 DP 表,每一行从左到右三个格子,分别代表选出的和除以 3 余 0、余 1、余 2 时的最大和。最上面一行是起点空集,往下每一行表示又把一个新数纳入考虑。我们从上往下、每行从左往右地填,每填一行就用上一行的结果推出来。最终答案不是某个中间格,而是最后一行最左边那个「余 0」格,因为它代表把所有数都考虑过、且总和能被 3 整除时的最大和。
起点 · 空集打地基：先填起点这一行,也就是一个数都还没选的状态。什么都不选,和是 0,而 0 除以 3 余 0,所以「余 0」那格填 0,这是一个完全合法的方案。可这时候你没法只靠空集就让和余 1 或者余 2,那两个状态根本还不存在,所以「余 1」「余 2」两格填一个极小的哨兵值,画面上用空集符号表示它们暂时接不上。地基打好,后面每来一个数都基于上一行往下推。
第 1 个数 3 · 填「余 0」：现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 0,前面那部分的余数就得是 0,因为 0 加 0 除以 3 正好余 0。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 0」的格子 f[0][0] = 0;二是把 3 接到上一行「余 0」那个最优和上,0 加 3 等于 3。两者取大,f[1][0] = 3,接上 3 更划算。
第 1 个数 3 · 填「余 1」：现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 1,前面那部分的余数就得是 1,因为 1 加 0 除以 3 正好余 1。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 1」的格子 f[0][1] = 空;二是把 3 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[1][1] = 空,两边一样大。
第 1 个数 3 · 填「余 2」：现在把第 1 个数 3 纳入考虑,它自己除以 3 余 0。要让总和余数变成 2,前面那部分的余数就得是 2,因为 2 加 0 除以 3 正好余 2。所以这一格有两个来源:一是不要 3,照搬上一行同样「余 2」的格子 f[0][2] = 空;二是把 3 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[1][2] = 空,两边一样大。
第 1 个数 3 · 这一行填完：把第 1 个数 3 的三列都算完了,这一行是 3、空、空。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 2 个数 6 · 填「余 0」：现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 0,前面那部分的余数就得是 0,因为 0 加 0 除以 3 正好余 0。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 0」的格子 f[1][0] = 3;二是把 6 接到上一行「余 0」那个最优和上,3 加 6 等于 9。两者取大,f[2][0] = 9,接上 6 更划算。
第 2 个数 6 · 填「余 1」：现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 1,前面那部分的余数就得是 1,因为 1 加 0 除以 3 正好余 1。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 1」的格子 f[1][1] = 空;二是把 6 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[2][1] = 空,两边一样大。
第 2 个数 6 · 填「余 2」：现在把第 2 个数 6 纳入考虑,它自己除以 3 余 0。要让总和余数变成 2,前面那部分的余数就得是 2,因为 2 加 0 除以 3 正好余 2。所以这一格有两个来源:一是不要 6,照搬上一行同样「余 2」的格子 f[1][2] = 空;二是把 6 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[2][2] = 空,两边一样大。
第 2 个数 6 · 这一行填完：把第 2 个数 6 的三列都算完了,这一行是 9、空、空。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 3 个数 5 · 填「余 0」：现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 0,前面那部分的余数就得是 1,因为 1 加 2 除以 3 正好余 0。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 0」的格子 f[2][0] = 9;二是把 5 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[3][0] = 9,不要 5 更划算。
第 3 个数 5 · 填「余 1」：现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 1,前面那部分的余数就得是 2,因为 2 加 2 除以 3 正好余 1。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 1」的格子 f[2][1] = 空;二是把 5 接到上一行「余 2」那个最优和上,可上一行「余 2」那格还是空的,这一支接不上。两者取大,f[3][1] = 空,两边一样大。
第 3 个数 5 · 填「余 2」：现在把第 3 个数 5 纳入考虑,它自己除以 3 余 2。要让总和余数变成 2,前面那部分的余数就得是 0,因为 0 加 2 除以 3 正好余 2。所以这一格有两个来源:一是不要 5,照搬上一行同样「余 2」的格子 f[2][2] = 空;二是把 5 接到上一行「余 0」那个最优和上,9 加 5 等于 14。两者取大,f[3][2] = 14,接上 5 更划算。
第 3 个数 5 · 这一行填完：把第 3 个数 5 的三列都算完了,这一行是 9、空、14。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 4 个数 1 · 填「余 0」：现在把第 4 个数 1 纳入考虑,它自己除以 3 余 1。要让总和余数变成 0,前面那部分的余数就得是 2,因为 2 加 1 除以 3 正好余 0。所以这一格有两个来源:一是不要 1,照搬上一行同样「余 0」的格子 f[3][0] = 9;二是把 1 接到上一行「余 2」那个最优和上,14 加 1 等于 15。两者取大,f[4][0] = 15,接上 1 更划算。
第 4 个数 1 · 填「余 1」：现在把第 4 个数 1 纳入考虑,它自己除以 3 余 1。要让总和余数变成 1,前面那部分的余数就得是 0,因为 0 加 1 除以 3 正好余 1。所以这一格有两个来源:一是不要 1,照搬上一行同样「余 1」的格子 f[3][1] = 空;二是把 1 接到上一行「余 0」那个最优和上,9 加 1 等于 10。两者取大,f[4][1] = 10,接上 1 更划算。
第 4 个数 1 · 填「余 2」：现在把第 4 个数 1 纳入考虑,它自己除以 3 余 1。要让总和余数变成 2,前面那部分的余数就得是 1,因为 1 加 1 除以 3 正好余 2。所以这一格有两个来源:一是不要 1,照搬上一行同样「余 2」的格子 f[3][2] = 14;二是把 1 接到上一行「余 1」那个最优和上,可上一行「余 1」那格还是空的,这一支接不上。两者取大,f[4][2] = 14,不要 1 更划算。
第 4 个数 1 · 这一行填完：把第 4 个数 1 的三列都算完了,这一行是 15、10、14。继续往下,基于这一行去考虑下一个数。注意「余 0」这一列一路在变大,但只有填到最后一行它才是真正的答案。
第 5 个数 8 · 填「余 0」：现在把第 5 个数 8 纳入考虑,它自己除以 3 余 2。要让总和余数变成 0,前面那部分的余数就得是 1,因为 1 加 2 除以 3 正好余 0。所以这一格有两个来源:一是不要 8,照搬上一行同样「余 0」的格子 f[4][0] = 15;二是把 8 接到上一行「余 1」那个最优和上,10 加 8 等于 18。两者取大,f[5][0] = 18,接上 8 更划算。
第 5 个数 8 · 填「余 1」：现在把第 5 个数 8 纳入考虑,它自己除以 3 余 2。要让总和余数变成 1,前面那部分的余数就得是 2,因为 2 加 2 除以 3 正好余 1。所以这一格有两个来源:一是不要 8,照搬上一行同样「余 1」的格子 f[4][1] = 10;二是把 8 接到上一行「余 2」那个最优和上,14 加 8 等于 22。两者取大,f[5][1] = 22,接上 8 更划算。
第 5 个数 8 · 填「余 2」：现在把第 5 个数 8 纳入考虑,它自己除以 3 余 2。要让总和余数变成 2,前面那部分的余数就得是 0,因为 0 加 2 除以 3 正好余 2。所以这一格有两个来源:一是不要 8,照搬上一行同样「余 2」的格子 f[4][2] = 14;二是把 8 接到上一行「余 0」那个最优和上,15 加 8 等于 23。两者取大,f[5][2] = 23,接上 8 更划算。
第 5 个数 8 · 这一行填完：把第 5 个数 8 的三列都算完了,这一行是 18、22、23。这是最后一行,最左边「余 0」格的 18 就是最终答案。
完成 · 答案 18：整张表填满了,最后一行「余 0」那格是 18,这就是答案。倒推一下它选了谁:全部五个数加起来是 3 加 6 加 5 加 1 加 8 等于 23,23 除以 3 余 2,要把余数清成 0,得舍掉余数为 2 的部分,这里舍掉的正是那个 5,剩下 3、6、1、8 加起来 18,正好能被 3 整除。算法没有真的去枚举舍谁,而是靠三列余数状态自动把这笔账算清了。
三个边界都能手验:单数凑不出时返回 0、总和余 2 时舍最小余 2 数、总和本就整除时全选。
面试三连:f[i][j] 按余数设状态加转移;可用贪心但要按余数分类讨论且可能减两个数;空间能滚动到 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxSumDivThree(self, nums: List[int]) -> int: n = len(nums) f = [[-inf] * 3 for _ in range(n + 1)] f[0][0] = 0 for i, x in enumerate(nums, 1): for j in range(3): f[i][j] = max(f[i - 1][j], f[i - 1][(j - x) % 3] + x) return f[n][0]复杂度
- 时间：O(n)，从头到尾扫一遍数组,每个数固定更新 3 个余数状态,3 是常数,所以总时间和数组长度成正比,n 到 4 万也是瞬间
- 空间：O(n)，按峰值算:参考代码开了一张 (n 加 1) 行乘 3 列的表 f,所以是 O(n)。因为每行只依赖上一行,完全可以只留 3 个滚动变量把空间压到 O(1)
易错点
面试追问把动画讲成自己的话
追问状态怎么设,转移是什么?
追问能不能用贪心代替 DP?
追问空间能压到 O(1) 吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计全 1 子矩形
LeetCode 1504 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题