2024多益网络笔试题（已凉）

题目 感觉还行

小红喜欢 3 的倍数的数字，现在小红有一个长度为 n的数字小红想通过分隔字符串的方式，获得一些子串，每个子串代表个数字，那么小红最多能获得多少个数字是3的倍数呢?
比如，小红有数字“1123，那么可以分隔为[1,12,3]，这样获得两个数字是3的倍数。
请注意，分隔后的数字串，不能包含前导零，比如 012 不能视12。可以分割出0，0也是3 的倍数。
输入描述
第一行输入一个没有前导零的正整数 1，表示小红的数字
1<n < 10105
输出描述
输出一个整数，表示小红能够获得的 3 的倍数的数字的最大数量。

def countMultiplesOfThree(n):
    # 将数字转换为字符串，方便遍历
    digits = str(n)
    length = len(digits)
    
    # 定义动态规划数组dp，dp[i]表示前i个数字中以第i个数字结尾的数字串中，最多能获得多少个数字是3的倍数
    dp = [0] * (length + 1)
    
    for i in range(1, length + 1):
        # 获取当前数字
        curr_digit = int(digits[i - 1])
        
        # 单独成为一个数字的情况
        if curr_digit % 3 == 0:
            dp[i] = max(dp[i], dp[i - 1] + 1)
        
        # 与前面的数字组成新的数字的情况
        for j in range(i - 1, 0, -1):
            num = int(digits[j - 1:i])
            if num % 3 == 0:
                dp[i] = max(dp[i], dp[j - 1] + 1)
    
    return dp[length]

# 读取输入
n = int(input())
# 调用函数并输出结果
print(countMultiplesOfThree(n))