【问题描述】 你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。 【输入格式】 输入的第一行包含一个整数 N。 第二行包含 N 个整数：W1, W2, W3, · · · , WN。 【输出格式】 输出一个整数代表答案。 【样例输入】 3 1 4 6 【样例输出】 10 【样例说明】 能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。 1 = 1； 2 = 6 − 4 (天平一边放 6，另一边放 4)； 3 = 4 − 1； 4 = 4； 5 = 6 − 1； 6 = 6； 7 = 1 + 6； 9 = 4 + 6 − 1； 10 = 4 + 6； 11 = 1 + 4 + 6。 【评测用例规模与约定】 对于 50% 的评测用例，1 ≤ N ≤ 15。 对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。

通过观察题目可以发现这是一道动规题，但和常规的动规题有一点区别，这道动规题含有减法项。 我的分析方法是，首先看所给变量参数，我们这里有：

砝码 i 每个砝码的重量w[i] (可以求得sum

先来说法一，该方法是套用 dp 模板，更好理解一些 。首先设dp[i][j] ,其中 **i 表示第 i 个砝码，j 表示前 i 个砝码刚好组成 j 重量的方法数。**接下来分析可以产生的两种情况 即：

1，如果 当前 j == w[i] ,即第 i 个砝码的重量正好等于 j 重量。那么只称重第 i 个砝码为一个方法数，再加上前 i-1个砝码组成 j 的方法数可以得到 dp[i][j]。 . 2，如果 j != w[i] ,即第 i 个砝码的重量可能小于或者大于需要组成的 j 的重量 ，那么我们可以选择称重该砝码或者不称重该砝码。假如不选，这个时候前 i 个砝码可以组成 j 重量的方法数为dp[i-1][j] ，假如选，这个时候前i-1个砝码所组成的重量是j-w[i], 也就是说前i个砝码中所有能凑出j-w[i]重量的方案再加上当前第i个砝码，就可以变成前i个砝码所组成重量为 j 的方案数。两种情况加起来可以得到 dp[i][j] 。

即

上代码