题解 | #称砝码#

看了这么多题解，关于Java形式的没有一个使用深度优先搜索的（dfs）；看到其中有个伙伴的题解提到了，但是考虑到最后一个用例超时，所以也放弃了dfs的方式；

dfs写出来之后其实可以进行剪枝优化，优化后也是能过全部用例的；我这里采用了记忆化搜索的方式，把已经走过的过程记录下来，不在进行递归，这样就能减少非常一大部分的情况了；

关键代码

private static void dfs(int[][] ints, int n, int i, Set<Integer> set, int count,
                          Map<String, Boolean> alreadyMap) {
    if (i == n) {
      set.add(count);
      return;
    }

    // 剪枝优化
    String key = i + "_" + count;
    if (alreadyMap.containsKey(key)) {
      return;
    }

    // 对于第i个元素，可以拿0个或者拿所有
    for (int j = 0; j <= ints[i][1]; j++) {
      int sum = j * ints[i][0];
      dfs(ints, n, i + 1, set, count + sum, alreadyMap);
    }
    alreadyMap.put(key, true);
  }

完整的代码

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static void dfs(int[][] ints, int n, int i, Set<Integer> set, int count,
                            Map<String, Boolean> alreadyMap) {
        if (i == n) {
            set.add(count);
            return;
        }

        // 剪枝优化
        String key = i + "_" + count;
        if (alreadyMap.containsKey(key)) {
            return;
        }

        // 对于第i个元素，可以拿0个或者拿所有
        for (int j = 0; j <= ints[i][1]; j++) {
            int sum = j * ints[i][0];
            dfs(ints, n, i + 1, set, count + sum, alreadyMap);
        }
        alreadyMap.put(key, true);
    }

    /*
    8
    69 54 119 85 103 53 155 170
    6 6 3 7 6 2 2 4

    10
    2000 1999 1998 1997 1996 1995 1994 1993 1992 1991
    10 10 10 10 10 10 10 10 10 10
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = Integer.parseInt(in.nextLine());

        int[][] ints = new int[n][2];

        for (int i = 0; i < n; i++) {
            ints[i][0] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            ints[i][1] = in.nextInt();
        }


        Set<Integer> set = new HashSet<>();
        dfs(ints, n, 0, set, 0, new HashMap<>());

        System.out.println(set.size());
        //  [29, 29, 108, 108, 108, 108, 108, 185]
    }



}