s******d
发帖数: 61 | 1 可以多余2个数,这题DP怎么做啊.......
还有
最经典的DP coin问题, careercup上是求所有可能的次数
public static int makeChange(int n, int denom){
int next_denom=0;
switch(denom){
case 25:
next_denom=10;
break;
case 10:
next_denom=5;
break;
case 5:
next_denom=1;
break;
case 1:
return 1;
}
int ways=0;
for(int i=0;i*denom
ways+=makeChange(n-i*denom,next_denom);
}
return ways;
}
如果要求print 所有的pair应该如果改code呢?
多谢多谢 | s*****y
发帖数: 897 | 2 recursive + backtracking. | s******d
发帖数: 61 | | I*******l
发帖数: 203 | 4 Maybe you can try the following: build a table Num[i], i=1,...n, to store
the number of ways summing some numbers in the array gives i. Then Num[n] is
what you want. Suppose the given array is A[1], ..., A[k], then the
recursion is Num[j]=\sum_{k: A[k]
different ways of choosing last element in your sum.
In the same way, you can solve the coin problem. | d*******d
发帖数: 2050 | 5 这不是dp coin问题,这是subset sum问题,经典的NPC问题.
【在 s******d 的大作中提到】
: 可以多余2个数,这题DP怎么做啊.......
: 还有
: 最经典的DP coin问题, careercup上是求所有可能的次数
: public static int makeChange(int n, int denom){
: int next_denom=0;
: switch(denom){
: case 25:
: next_denom=10;
: break;
: case 10:
|
|
