9.5 小米笔试 软件

第二题 记忆化搜索，有没有大佬帮忙看看对吗？

笔试的时候少加了 ans = Math.min(ans, dfs(i, a, memo, sum + 1, x) + 1); 这一行，当时以为一个数只能操作一次，不知道现在对了没有...

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = reader.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]), x = Integer.parseInt(inputs[1]);
        int[] a = new int[n];
        String[] as = reader.readLine().split(" ");
	  	// 当前累计和
        int sum = 0;
	  
        for (int i = 0; i < as.length; ++ i) {
            a[i] = Integer.parseInt(as[i]);
            sum += a[i];
        }
        int[][] memo = new int[n][sum * 2 + 1];
	  
        for (int[] row : memo) Arrays.fill(row, -1);
	  
        System.out.println(dfs(n - 1, a, memo, sum, x));
    }
    
    private static int dfs(int i, int[] a, int[][] memo, int sum, int x) {
        if (sum % x == 0) return 0;
        if (i < 0) return 1005;

        if (memo[i][sum] != -1) return memo[i][sum];
        // 操作
        int ans = Math.min(dfs(i - 1, a, memo, sum + 1, x), dfs(i - 1, a, memo, sum - a[i], x)) + 1;
        
        // 不操作
        ans = Math.min(ans, dfs(i - 1, a, memo, sum, x));
        // 对当前位置多次操作
        ans = Math.min(ans, dfs(i, a, memo, sum + 1, x) + 1);


        return memo[i][sum] = ans;
    }
}