gpt4 book ai didi

java - 使用动态规划改变硬币

转载 作者:行者123 更新时间:2023-11-29 02:58:25 26 4
gpt4 key购买 nike

换硬币是一个很受欢迎的面试问题。本质上,这个问题意味着给定一组硬币面额和总数,如果每种面额的硬币都有无限供应,那么有多少种方法可以获得总数。

这是我的代码。逻辑是每次我选择一枚硬币时,问题都会减少到解决总数减去硬币的问题。

public static int numberOfWays(int total, int[] options){

int[][] memo = new int[options.length][total+1];

for (int i = 0; i <memo.length ; i++) {

for (int j = 0; j <memo[i].length ; j++) {

if(i == 0) memo[i][j] = 1;
else if(options[i] > j ) memo[i][j] = memo[i-1][j];
else memo[i][j] = memo[i-1][j] + memo[i][j - options[i]];
}
}
return memo[options.length-1][total];
}

这适用于 total = 5 和 options = 1, 2, 3 的测试用例但失败 total = 10 and options = 2, 5, 3, 6

谁能帮助我理解我做错了什么。

最佳答案

首先,最好写出每个数组元素代表什么的声明:

memo[i][j] represents how many ways to make the total amount j given only coins in denominations options[0], options[1], ..., options[i].

现在,您似乎从中推导出了一些定律:

  1. memo[0][j]1对于所有 j
  2. i大于 0,memo[i][j]memo[i-1][j]相同每当options[i] > j
  3. i大于 0,memo[i][j]memo[i-1][j] + memo[i][j - options[i]]每当options[i] <= j

你的问题是这些定律中的第一个是不正确的。 (后面两个是)

声明“memo[0][j] is 1 for all j”仅在options[0] 时成立是1 .如果options[0]不是 1 , 然后 memo[0][j]j 时为 1是 options[0] 的倍数, 如果不是则为 0。仅使用面额硬币 2 ,你赚不到 5 美分,所以你应该有(第二组数据)memo[0][5] == 0 , 但你的程序说 memo[0][5] == 1 .然后,这会抛出所有后续计算。

所以我会修改你的程序说:

            if(i == 0) { if (j % options[i] == 0) memo[i][j] = 1;
else memo[i][j] = 0; }
else if(options[i] > j ) memo[i][j] = memo[i-1][j];
else memo[i][j] = memo[i-1][j] + memo[i][j - options[i]];

(尽管就纯粹的文体注释而言,我发现 if/else 即使是单个语句也不使用大括号的语句是在询问错误)

关于java - 使用动态规划改变硬币,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36696667/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com