Блог

Учитывая оценки для отдельных игр и конечную целевую оценку, цель состоит в том, чтобы вычислить количество возможных комбинаций. (например, если целевой балл равен 6, а игровые баллы <1,3>, есть 3 способа достичь целевого балла — 3×2, 3×1 1×3, 1×6)

Я не понимаю, почему мой код неправильный:

 import java.util.*;
public class Main
{
    public static int combinations(int target, List<Integer> plays) {
        Collections.sort(plays);
        HashMap<Integer, Integer> map = new HashMap<>(); //map score to combinations. 
        map.put(0,1);
        combHelper(target,plays,plays.size() -1, map);
        return map.get(target);
        
    }
    
    private static int combHelper(int target, List<Integer> plays, int i, HashMap<Integer, Integer> map) {
        if (target < 0 || i < 0) {
            return 0;
        }
        if (!map.containsKey(target)) {
            int out = combHelper(target,plays,i - 1, map)   combHelper(target - plays.get(i),plays,i,map);
            map.put(target,out);
        }
        return map.get(target);
    }
    
    public static void main(String[] args) {
        List<Integer> points = new ArrayList<>(Arrays.asList(3,1));
        System.out.println(combinations(6,points)); //output is 2
    }
}

  

любая помощь и отзывы будут оценены!

Я не знаю, что не так с вашим кодом, но он выглядит сложным для понимания.

Существует более простой и простой способ решить эту проблему без рекурсии.

Шаги:

• создайте массив dp с размером target 1
• для каждой точки в points обновлении dp

 import java.util.List;
import java.util.Arrays;

public class Main
{   
    static int noOfWays(List<Integer> points, int target) {
        
        int[] dp = new int[target   1];
        dp[0] = 1;
        for(int point: points)
            for(int i = point; i <= target; i  )
                dp[i]  = dp[i - point];

        return dp[target];
    }

    public static void main(String[] args) {
        List<Integer> points = Arrays.asList(1, 3);
        int target = 6;
        System.out.println(noOfWays(points, target));
    }
}