这段动态编程代码有什么问题？

Question

你好这是我第一次在这个社区发帖

所以，我需要做的是：

编写一个函数 canSum()，将目标总和和数字数组作为参数。

该函数应该 return 一个布尔值，指示是否可以使用数组中的数字生成目标总和。

您可以根据需要多次使用数组的元素

您可以假设所有输入数字都是非负数。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        System.out.println(canSum(7, new int[]{2, 3}));         //true
        System.out.println(canSum(7, new int[]{5, 3, 4, 7}));   //true
        System.out.println(canSum(7, new int[]{2, 4}));         //false
        System.out.println(canSum(8, new int[]{2, 3, 5}));      //true
        System.out.println(canSum(300, new int[]{7, 14}));      //false

    }
    private static Map<Integer, Boolean> memo = new HashMap<>();

    public static boolean canSum(int target, int[] arr){

        if(memo.containsKey(target)) return memo.get(target);
        if(target == 0) return true;
        if(target < 0) return false;

        for(int i = 0; i< arr.length;i++){
            int remainder = target - arr[i];
            if(canSum(remainder,arr)){
                memo.put(target, true);
                return true;
            }
        }
        memo.put(target,false);
        return false;
    }

程序输出：真的真的真的真的真

什么时候应该：真的真的错误的真的假

Answer 1

您的问题是您从不在方法调用之间清除 Map<Integer, Boolean> memo。如果可以使用 true 或 false 生成总和，则保存的映射仅对一种方法有效运行，因此您的代码不应在不同调用之间重复使用相同的映射。

一个简单的解决方法是在每次调用后手动清除地图：

System.out.println(canSum(7, new int[] { 2, 3 })); //true
memo.clear();
System.out.println(canSum(7, new int[] { 5, 3, 4, 7 })); //true
memo.clear();
System.out.println(canSum(7, new int[] { 2, 4 })); //false
memo.clear();
System.out.println(canSum(8, new int[] { 2, 3, 5 })); //true
memo.clear();
System.out.println(canSum(300, new int[] { 7, 14 })); //false
memo.clear();

将创建输出

true
true
false
true
false

一个更优雅的解决方案是不使用字段来存储地图，而是在需要时在内部创建它。您可以使用 2 种方法这样做，例如：

public static boolean canSum(int target, int[] arr) {
    Map<Integer, Boolean> memo = new HashMap<>();
    return canSum(target, arr, memo);
}

private static boolean canSum(int target, int[] arr, Map<Integer, Boolean> memo) {
    if (memo.containsKey(target)) {
        return memo.get(target);
    }
    if (target == 0) {
        return true;
    }
    if (target < 0) {
        return false;
    }

    for (int i = 0; i < arr.length; i++) {
        int remainder = target - arr[i];
        if (canSum(remainder, arr, memo)) {
            memo.put(target, true);
            return true;
        }
    }
    memo.put(target, false);
    return false;
}

Answer 2

它不起作用，因为您的 memo 地图是一个静态成员变量，它也将包含所有以前的迭代。

因此，当您在最后一行中执行 memo.put() 时，它添加了不同的组合，这些组合直接在 memo.containsKey 中重复使用。

您可以在该函数内移动该变量。它应该开始正常工作。

Answer 3

不要把备忘录当作静态的

public class Main {
    public static void main(String[] args) {
        System.out.println(canSum(7, new int[]{2, 3}));         //true
        System.out.println(canSum(7, new int[]{5, 3, 4, 7}));   //true
        System.out.println(canSum(7, new int[]{2, 4}));         //false
        System.out.println(canSum(8, new int[]{2, 3, 5}));      //true
        System.out.println(canSum(300, new int[]{7, 14}));      //false

    }
    /* 
     * private static Map<Integer, Boolean> memo = new HashMap<>(); 
     * 
     * It will check for first one and will store the result, then for rest
     * operation it will rend stored data only
     */

    public static boolean canSum(int target, int[] arr){
        
        Map<Integer, Boolean> memo = new HashMap<>();

        if(memo.containsKey(target)) return memo.get(target);
        if(target == 0) return true;
        if(target < 0) return false;

        for(int i = 0; i< arr.length;i++){
            int remainder = target - arr[i];
            if(canSum(remainder,arr)){
                memo.put(target, true);
                return true;
            }
        }
        memo.put(target,false);
        return false;
    }
}

Answer 4

您应该将备忘录对象作为函数参数并将其默认值设置为None。这样就不会混淆全局作用域和每次调用函数时清除memo对象了。

简单的伪代码：

def canSum(targetSum: int, numbers: list[int], memo=Optional[dict] = None) -> Bool:
    # Memo Checking Logic
    if memo is None:
        memo = {}

    # Base Cases
    # Memo Fetching Logic
    if targetSum in memo:
        return memo[targetSum]

    if targetSum < 0:
        return False

    if targetSum == 0:
        return True

    # Recursive Case
    for num in numbers:
        remainder = targetSum - num
        # Memo Caching Logic
        if canSum(remainder, numbers, memo):
            memo[targetSum] = True
            return True

    memo[targetSum] = False
    return False

这段动态编程代码有什么问题？

what is wrong in this code for dynamic programming?

java

dynamic-programming