英文:
Restricted Coin change problem python java conversion
问题
// cs is a list of pairs (c, k) where there's k
// coins of value c.
public static int limitedCoins(int[][] cs, int n) {
int[] r = new int[n + 1];
r[0] = 1;
for (int i = 0; i < cs.length; i++) {
int c = cs[i][0];
int k = cs[i][1];
int[] rs = r.clone();
for (int j = c; j <= n; j++) {
rs[j] += rs[j - c];
// This line effectively performs:
// r'[j] = sum(r[j - j * c] for j = 0...k)
// but using rs[] so that the computation is O(1)
// and in place.
r[j] += rs[j - c] - (j < c * (k + 1) ? 0 : rs[j - c * (k + 1)]);
}
}
return r[n];
}
for (int n = 0; n < 50; n++) {
System.out.println(n + " " + limitedCoins(new int[][]{{1, 3}, {2, 2}, {5, 3}, {10, 2}}, n));
}
英文:
I have a python function from
https://stackoverflow.com/a/44214566/6301603
Which calculates the amount of possible coin changes. Where each coin has a limited avaibility. I tried to understand it to convert it to java but i failed in the line r= can somebody explain whats happening in this line?
# cs is a list of pairs (c, k) where there's k
# coins of value c.
def limited_coins(cs, n):
r = [1] + [0] * n
for c, k in cs:
# rs[i] will contain the sum r[i] + r[i-c] + r[i-2c] + ...
rs = r[:]
for i in xrange(c, n+1):
rs[i] += rs[i-c]
# This line effectively performs:
# r'[i] = sum(r[i-j*c] for j=0...k)
# but using rs[] so that the computation is O(1)
# and in place.
r[i] += rs[i-c] - (0 if i<c*(k+1) else rs[i-c*(k+1)])
return r[n]
for n in xrange(50):
print n, limited_coins([(1, 3), (2, 2), (5, 3), (10, 2)], n)
Thanks
答案1
得分: 0
用以下代码替换那行代码：
int[] r = new int[n+1];
r[0] = 1;
for (int i = 1; i < r.length; i++)
r[i] = 0;
英文:
Replace that line with
int[] r = new int[n+1];
r[0] = 1;
for (int i = 1; i < r.length; i++)
r[i] = 0;
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论