数位染色

[编程题]数位染色

热度指数：3994 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红拿到了一个正整数 $x\$ 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。
她不知道能不能达成目标。你能告诉她吗？

输入描述:

一个正整数  ，

输出描述:

如果小红能按要求完成染色，输出"Yes"。否则输出"No"。

示例1

输入

输出

Yes

说明

将3、4、7染成红色即可，这样3+4+7=1+2+5+6

示例2

输入

输出

No

说明

显然无论如何都不能完成染色。

算法知识视频讲解

Python 3

牛客760622808号

补充一个python版

def ans():
    nums = list(map(int , list(input())))
    sum_num = sum(nums)
    if sum_num % 2 == 1:
        print("No")
        return
    else:
        target = sum_num // 2
    dp = [0] * (target+1)
    dp[0] = 1
    for n in nums:
        j = target
        while j >= n:
            dp[j] += dp[j-n]
            j -= 1
    res = "Yes" if dp[target] else "No"
    print(res)
ans()

发表于 2021-11-04 13:23:11 回复(1)