a = input() dp = [0,0,0] for i in range(len(a)): if int(a[i]) % 3 == 0: dp = [e * 2 for e in dp] dp[0] += 1 if int(a[i]) % 3 == 1: temp = dp[:] dp[1] += temp[0] dp[2] += temp[1] dp[0] += temp[2] dp[1] += 1 if int(a[i]) % 3 == 2: temp = dp[:] dp[2] += temp[0] dp[0] += temp[1] dp[1] += temp[2] dp[2] += 1 print(dp[0])
思路：
把输入读到变量a以后，对其中每一个字符遍历
给定一个数组dp， 包含前i项组成的字符串子序列中 被3除后余数为 0 1 2 的个数
向后延伸，如果新的数自身能被3除尽（余数为0），则dp每一项都变为原来的2倍【因为加到任意序列后面，除以3余数不变】，当然它自身也能组成一个余数为0的子序列，因此dp[0]加一
同理，推理如果新的数被3除余1和余2的情况，和原本不同余数的子序列组合分别会生成不同的情况
全部评论
(0) 回帖