分数组合数，动态规划帮助，（来自编程面试要素，java）

Question

给定个人比赛得分和最终目标得分，objective 是计算可能组合的数量。（例如，如果目标分数为 6，播放分数为 <1,3>，则有 3 种方法可以达到目标分数 - 3x2、3x1 + 1x3、1x6）

我看不出为什么我的代码是错误的：

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
    }
}

如有任何帮助和反馈，我们将不胜感激！

Answer 1

我不知道你的代码有什么问题，但看起来很难理解。

有一种更简单、更容易的解决方法，无需递归。

步骤：

创建一个数组 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));
    }
}

分数组合数，动态规划帮助，（来自编程面试要素，java）

Number of score combinations, dynamic programming help, ( from elements of programming interviews, java)

java

recursion

dynamic-programming