1000ms

Difficulty: 9

所属公司 : oppo

时间 :2024年8月24日场

算法与标签>动态规划

会员专享

请先登录，开通会员或购买该题目所属题库（oppo机考题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（oppo机考题库），可解锁完整内容。

购买题库开通会员

思路:动态规划

1.我们知道，一个数是3的倍数等价于它的数位和是 3的倍数。也就是数位和%3=0

然后我们知道0~9里有 4个%3=0的数 , 分别是0,3,6,9 3个%3=1的数 , 分别是1,4,7 3个%3=2的数 , 分别是2,5,8

所以考虑动态规划: $dp[i][j]$ 表示前i个数模3余j的方案数

题目内容

小红有一个长度为 $n$ 的数字字符串 $s$ ，但其中有一些数位被墨水覆盖看不清了。他现在想知道，有多少种可能的数字使得 $s$ 是3的倍数（注意： $s$ 不含前导零）。