题解 | #称砝码#动态规划
称砝码
https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
题目分析:
可以直接看成:给n个砝码,求能称出的不同的重量数。
暂不考虑质量相同的砝码怎么办,一视同仁
方法一:Set直接去重
假设有3个砝码,质量分别为:1、1、2。
1个砝码都没可以称出的结果:0。
加第1个砝码可以称出的结果:0 、1。
加第2个砝码可以称出的结果:0 、1、2。
加第2个砝码可以称出的结果:0 、1、2、3、4。
规律就是,当我每次加一个砝码,就有两种情况。
情况一:我不用这个砝码,那可以称出的结果就是上一次的结果,保持不变。
情况二:我用这个砝码,那就是上一次可以称出的结果加上这个砝码质量
把情况一和情况二加起来,去重(用set),就是当前能称出的质量
//关键代码类似如下 //1、遍历每一个砝码,当前砝码的质量为m。类似于我循环地去外面拿一个砝码,质量为m. for (Integer m : fama) { //2、拿到砝码后,需要对没拿砝码前的所有可以称出的结果进行遍历, for (Integer temp : result_set) { //3、没拿砝码前的所有可以称出的结果加上当前拿的砝码 result.add(temp + m ); //4、集合本身里面就已经有上一次的结果,所以直接把情况二的结果放进去就可以 } }
方法二:动态规划
给一堆砝码,能称出的最小质量为0,最大质量是所有砝码的总和, 假设最大值为max。所以可以定义
dp = new boolean[max +1]
然后从0到max,遍历dp数组,如果质量n可以称的出,那么dp[n]=true,否则是false。统计dp数组中true的个数就是结果。
关键点:怎么判断一个质量能不能被称的出呢?
假设需要称一个质量n,其中有一个砝码质量为m1,如果n能被这堆砝码称出来,那么n-m1这个质量肯定也可以称出来。
所以要称n ,那就先称n-m1,然后称n-m1时,同理它又得先称n-m1-m2。一直到0。
boolean[] dp = new boolean[max+1]; dp[0] = true; int count = 1; for (Integer m : fama) { //循环每一个砝码 for (int i = max; i >= m; i--) { if (dp[i-m] && !dp[i]){ dp[i] = true; count++; } } } System.out.println(count);