最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

算法练习:给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除

XAMPP案例 admin 110浏览 0评论

给你一个长度为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

es00000093

code as followed:

s = input()
mod = 1000000007
dp = [[0] * 3 for _ in range (51)] # 定义动态规划数组
for i in range (1, len(s)+1):
    m = int(s[i-1])%3 
    dp[i][m] = 1
    for j in range (3):
        dp[i][j] += (dp[i-1][j] + dp[i-1][(j+3-m)%3]) % mod
print(dp[len(s)][0])

这道题目解决后,以后遇到在类似的题目就可以直接套用这个方法来做,比如猿辅导之前被5整除的最大子序列个数。

转载请注明:XAMPP中文组官网 » 算法练习:给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除