给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除答案对1e9+7取模
解析：这道题目其实很有意思，他的难点在于我们需要求的序列是可连续可不连续的，如[1,2,3,4,5]，答案有11种，[1,2],[1,2,3],[1,2,4,5],[1,2,3,4,5],[1,3,5],[1,5],[2,4],[2,3,4],[3],[3,4,5],[4,5]。很明显我们需要使用动态规划算法，从一个个的子结果最终得到总结果。考虑到数字要被3整除，那么对3取余有三种情况，整除、余数为1，余数为2。而我们可以发现，若余数和也能被3整除的话那么这些余数本身的数字相加也能被3整除，如下图，第二行第一个位置的余数为0，那么他的最大子序列就是第一行的第二列、第三列的和，因为他们加起来是3的余数。
根据这个小规律我们可以定义一个二维的动态规划数组，其中i代表的是遍历到哪一个数字，j代表的是当前数字取余的具体情况，状态转移方程为dp[i][j] += (dp[i-1][j] + dp[i-1][(j+3-m)%3]) % mod
code as followed：
s = input()mod = 1000000007dp = [[0] * 3 for _ in range (51)] # 定义动态规划数组for i in range (1, len(s)+1):m = int(s[i-1])%3dp[i][m] = 1for j in range (3):dp[i][j] += (dp[i-1][j] + dp[i-1][(j+3-m)%3]) % modprint(dp[len(s)][0])
这道题目解决后，以后遇到在类似的题目就可以直接套用这个方法来做，比如猿辅导之前被5整除的最大子序列个数。