如果所有的数字和加起来能被3整除，那么我们必然会选择所有的数字。
如果所有的数字和加起来能被3除余1，那么我们必然会优先删除最小的一个被3除余1的数字。如果这个方法不存在，那么我们会删除最小的两个被3除余2的数字。
如果所有的数字和加起来能被3除余2，那么我们必然会优先删除最小的一个被3除余2的数字。如果这个方法不存在，那么我们会删除最小的两个被3除余1的数字。
此题和1262.Greatest-Sum-Divisible-by-Three非常相似，因此我们同样可以用动态规划来解决。在这里我们定义dp[i][j]表示前i个数字能组成的、被3除余j的最大字符串。此外我们还需要将digits按照从大到小的顺序排序。这样对于相同长度、余数相同的字符串，所选字符在digits里越靠前（即用了更大的字符），组成的字符串就越大。
状态转移返程的入手点依然是第i个元素是否采用。如果不采用，那么dp[i][j]=dp[i-1][j]. 如果采用，那么dp[i][j] = dp[i-1][j-digits[i]%3+3)%3] + to_string(digits[i]).那么这两种方案哪个更优呢？显然长度更长的字符串更优。但是如果长度相同呢？答案是前者更优。因为相同长度的两个字符串，前者用了更大的字符，而后者因为用了digits[i]必然会更小。
最后的答案是dp[n][0]。
解法2中的dp[i][j]会存储大量的字符串，效率很低。事实上我们不需要把每个状态(i,j)对应的字符串都存下来。我们只需要知道两个信息就能重构整个字符串：
- 考察(i,j)的最优解时，我们是否采用digits[i]?
- 考察(i,j)的最优解时，我们是从哪个状态跳转过来的？也就是它的前驱状态是(i-1,?)
如果记录下这两个信息（分别定义为pick[i][j]和prev[i][j]），所以我们只要从i=n, j=0开始，按i的递减顺序一步一步往前逆推我们的决策。对于(i,j)，pick[i][j]告诉我们是否选择了digits[i]；prev[i][j]则告诉我们(i,j)是从(i-1, prev[i][j])跳转过来的，所以我们下一回要更新i=i-1, j=prev[i][j]。直至回推到i=1为止。