十二届蓝桥杯 砝码称重（python）

十二届蓝桥杯 砝码称重（python）

 动态规划三大题型：计数问题、最值问题、存在性问题。

该题问可以称出多少种不同的重量，属于计数题型。

动态规划实现思路

从一个砝码开始，每个状态列举出当前可以被称出的重量；每次加入一个砝码，这时只需要将上一个状态的每个可以被称出的重量与新的砝码进行组合，即得出当前砝码数量可以被称出的所有重量；一直到最后一个砝码加入，最后一个状态就得出了所有可以被称出的重量

样例输入：3  1  4  6

加入第一个砝码1（状态1）       只能称出重量1

加入第二个砝码4 （状态2）        自身4可以称出        在1的状态1下更新1+4=5，4-1=3，就是1，3，4，5；

加入第三个砝码6          自身6可以称出        在状态2下更新1+6=7，6-1=5，3+6=9，6-3=3，4+6=10，6-4=2，5+6=11，6-5=1，就是1，2，3，4，5，6，7，9，10，11；

 

number = int(input())  # 砝码数量
arr = list(map(int, input().split()))
summ = sum(arr)
# 动态规划数组  dp[i][j]代表加入第i个砝码时，能不能称出重量j
dp = [[False for l in range(summ + 1)] for h in range(number + 1)]

dp[1][arr[0]] = True  # 第一个砝码的重量肯定可以被秤出来
for i in range(2, number + 1):  # 从第二个砝码开始
    for j in range(1, summ + 1):  # 复制上一组的状态
        dp[i][j] = dp[i - 1][j]
    weight = arr[i - 1]  # 当前砝码的重量
    dp[i][weight] = True  # 当前重量可以被称量
    for j in range(1, summ + 1):  # 在第一砝码的状态下更行第二个砝码的状态
        if dp[i - 1][j]:  # 如果第一个砝码能称出重量j  在此基础上加减
            dp[i][j + weight] = True
            dp[i][abs(j - weight)] = True

count = 0
for j in range(1, summ + 1):
    if dp[number][j]:
        count += 1
print(count)

 

在蓝桥杯练习系统上通过80%的测试用例，有没有大哥帮忙优化一下。