问题描述：你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · WN
请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边
输入的第一行包含一个整数 N
第二行包含 N 个整数：W1, W2, W3, · · · WN输出一个整数代表答案
输出一个整数代表答案
样例输入
3
1 4 6
样例输出
10
本篇博客主要是为了帮助同学更好初步理解动态规划，主要从分析的角度展开，代码是下面这位大佬原创哈不是我
第十二届蓝桥杯砝码称重问题——python_Prescu的博客-CSDN博客_python砝码称重
方法一（O(n²)）：从第一个开始计算，用l2辅助存储当前前i个砝码可以称的重量（q、q+i、abs（q-i）），每次加一个砝码带入计算更新l2、l3。（此方法会超时） n=int(input()) l1=list(map(int,input().split())) l2=[] l2.append(l1[0]) l3=[] for i in l1[1:]: for q in l2: if i not in l3:
https://blog.csdn.net/qq_40280704/article/details/121080383?utm_source=app&app_version=4.21.1
n=int(input()) a=list(map(int,input().split())) sum=0 for i in a: sum+=i dp=[[0]*2*sum for i in range(n+1)] result=0 for p in range(1,n+1): for q in range(1,sum+1): dp[p][q]=dp[p-1][q] if dp[p][q] == 0: if a[p-1]==q: dp[p][q]=1 if dp[p-1][a[p-1]+q]: dp[p][q]=1 print(p,q) if dp[p-1][abs(a[p-1]-q)]: dp[p][q]=1 for i in dp[n]: if i==1: result+=1 print(result)
输入格式就不解释了!哈 sum就是对所有砝码重量求和
创建dp[p][q]
疑问1：
为什么dp[p]=2*sum*[0]？>>防止index out of range索引越界......因为a[p-1]<sum,q<=sum,所以取2保证不越界
为什么是2？不可以是3吗？>>先给出结论：大于等于2都可以
疑问2：
p,q的含义 dp[p]代表加上第p个砝码之后 所能称出的所有情况
若dp[p][q]=1 代表加上第p个砝码之后 q的情况可以被测出 ...所以为0就是测不出来拉-。 -
其次 a[p-1]代表加上的那第p个砝码的单个重量
创建两层循环
疑问1：p,q的范围怎么知道的？>>假设给你3个砝码，当然是从1 考虑到 3 鸭....最后的答案就是根据dp[3]里面出现的1的次数确定(也就是最后四行代码的含义所在)>>再假设给你的那3个砝码是 1 4 6 不管你怎么称 最大的情况就是全部数字加起来，最小的情况就是最小的数字
赋值 dp[p][q]=dp[p-1][q]
疑问：为什么要这么赋值？>>拿我们刚刚砝码来说（假设重量未知哈），假设你已经知道加上第二个砝码后 可以称出q的重量 ，那现在轮到加第三个砝码，q的重量能否称出来？当然是可以的呀，你不要放第三个砝码就行了莫~所以如果dp[p][q]=1 此后下面的语句都不执行
来到最难理解也是最关键的代码段:
首先 思考你现在有三样东西：手中拿着的砝码a[p-1](第p个砝码),上一轮所能测出重量的所有数据dp[p-1],待测数据q
q从1--sum遍历访问，首先q在上一轮一定是不能测出来，所以我要在这一轮尝试测出来：测出一组数据需要两样东西 一个是你手里的砝码 一个是你已知的重量数据（你可能会问数据是数据，砝码是砝码，两个不同的东西怎么能放在一块测量？），不用着急，那我们就先忽略‘重量数据呗’。也就是说，如果你现在手里的砝码已经可以测成p(a[p-1]=q)，那不就好了吗，直接令d[p][q]=1,然后下面的代码执不执行都已经不影响了，因为就算执行了也还是让他变成1，不执行也还是1。下面讨论当你手里砝码不满足上面的情况的时候，重量数据就要派上用场了。首先要获得待测数据q，就要在天平的两侧或一侧分配砝码。考虑比较简单的情况，如果手里的砝码能和已有的重量数据dp[p-1](集合)中的X相加能组成q，即满足 a[p-1]+X=q (X∈dp[-1]），也就是说：敲重点:如果dp[p-1]中存在一个X等于 q-a[p-1]，那么p就可以被测出来！但这里有个隐藏条件就是q>=a[p-1]。同样的如果q+X=a[p-1]（手里的砝码若由待测数据和已知重量数据相加），同理如果dp[p-1]中存在一个X等于 a[p-1]-q，那么p就可以被测出来！综上：若dp[p-1][abs(a[p-1]-q)]则dp[p][q]=1(奇妙吧）还有一种情况，坚持坚持！上面说的两种情况都是把手里的砝码和重量数据放在两边，如果放在一边会怎么样？也就是X=q+a[p-1]如果dp[p-1]中存在一个X等于 q+a[p-1]，那么p就可以被测出来！
事实上，q=a[p-1]+X或a[p-1]-X或X-a[p-1]，就是说用你手中的两把数据去创造一个新的数据，如果新的数据等于q，等于说你可以在已有的数据条件下组合出q。然后再将问题转化为X的存在性问题，最后得出结论。
写在最后：博主也是第一次接触动态规划，实在做不出题目才去参考了大佬的代码，然后经过仔细思考，希望通过这篇详细的分析帮助更多和博主一样的小白对动态规划具体是怎么操作的在一个例题中有个初步了解，多有不足之处，恳请谅解，欢迎批评指正 【元旦快乐！】
