S********s
发帖数: 29 | 1 是Facebook发的准备材料上的题目：
An atm can only dispense values of $1, $5, $20, and $50. Return the number
of unique ways that a $ amount of X can be tendered.
($1, $5) is distinct from ($5, $1)
Input: 4 Output: 1
Input: 6 Output: 3
Input: 100 Output: 954515231698
按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
private static Integer atm(Integer x) {
if (x <= 0)
return x == 0 ? 1 : 0;
return atm(x - 1) + atm(x - 5) + atm(x - 20) + atm(x - 100);
} |
D*******a
发帖数: 3688 | 2 use an array to cache the result of atm(x) so you don't overflow the stack.
【在 S********s 的大作中提到】
: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)
|
h****t
发帖数: 69 | 3 Leetcode climbing stairs 的变形题， 用DP. Return long. |
I*******g
发帖数: 7600 | 4 我输入1000的时候， 都没有溢出
结果是
3809781405817283560133557648078873264200227888228196162666466870535154840891
97209663212281002759381072062453715265566609468
【在 S********s 的大作中提到】
: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)
|
m********3
发帖数: 4806 | |
z***m
发帖数: 1602 | 6 用dp，把前面的结果存起来
coin change problem的变形
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha
【在 S********s 的大作中提到】
: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)
|
c*****m
发帖数: 271 | |
t*******e
发帖数: 274 | 8
楼主的题目是前后次序有影响，在此基础上该怎么改？
【在 z***m 的大作中提到】
: 用dp，把前面的结果存起来
: coin change problem的变形
: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha
|
z***m
发帖数: 1602 | 9 对每个case，直接乘以 n!,.
比如算出的C[1,5]为x，直接乘以2。 如果是C[1 2 5]就乘以3！
【在 t*******e 的大作中提到】
:
: 楼主的题目是前后次序有影响，在此基础上该怎么改？
|
t*******e
发帖数: 274 | 10
不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
代码你是怎么做的么
【在 z***m 的大作中提到】
: 对每个case，直接乘以 n!,.
: 比如算出的C[1,5]为x，直接乘以2。 如果是C[1 2 5]就乘以3！
|
|
|
y*********8
发帖数: 387 | |
w*******i
发帖数: 186 | 12 感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个Set
Long>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
列数目，然后在set里求和。
另外dp表可以用长度为50的滚动数组，减少内存开销。 |
p**t
发帖数: 157 | 13 已知组合数 求排列数不需要具体列出来所有的排列吧。。。
【在 w*******i 的大作中提到】
: 感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个Set: Long>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
: 列数目，然后在set里求和。
: 另外dp表可以用长度为50的滚动数组，减少内存开销。
|
z***m
发帖数: 1602 | 14 找unique的元素个数，设为n，然后乘以n！
【在 t*******e 的大作中提到】
:
: 不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
: 代码你是怎么做的么
|
y*****h
发帖数: 22 | 15 这样可以不可以？
public long tellMoneyCombinations(int money) {
long[] f = new long[money+1];
f[0] = f[1] = 1;
for(int i=2; i<=money; i++) {
f[i] = f[i-1];
if(i>=5) f[i]+=f[i-5];
if(i>=20) f[i]+=f[i-20];
if(i>=50) f[i]+=f[i-50];
}
return f[money];
} |
s*******z
发帖数: 14 | 16 动态规划。
问下楼主，我怎么没看到有准备材料？就是HR邮件里面那一堆么？ |
s*******z
发帖数: 14 | 17 这样不可以。有重复的
【在 y*****h 的大作中提到】
: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }
|
t*****a
发帖数: 106 | 18 这个是对的
【在 y*****h 的大作中提到】
: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }
|
t*****a
发帖数: 106 | 19 题目就是要有重复的。
【在 s*******z 的大作中提到】
: 这样不可以。有重复的
|
x*******9
发帖数: 138 | 20 一般情况下，在OJ上，这种DP题都是让你MOD一个大质数的。
所以不用太担心溢出。
gl, hf |
|
|
S********s
发帖数: 29 | 21 是Facebook发的准备材料上的题目：
An atm can only dispense values of $1, $5, $20, and $50. Return the number
of unique ways that a $ amount of X can be tendered.
($1, $5) is distinct from ($5, $1)
Input: 4 Output: 1
Input: 6 Output: 3
Input: 100 Output: 954515231698
按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
private static Integer atm(Integer x) {
if (x <= 0)
return x == 0 ? 1 : 0;
return atm(x - 1) + atm(x - 5) + atm(x - 20) + atm(x - 100);
} |
D*******a
发帖数: 3688 | 22 use an array to cache the result of atm(x) so you don't overflow the stack.
【在 S********s 的大作中提到】
: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)
|
h****t
发帖数: 69 | 23 Leetcode climbing stairs 的变形题， 用DP. Return long. |
I*******g
发帖数: 7600 | 24 我输入1000的时候， 都没有溢出
结果是
3809781405817283560133557648078873264200227888228196162666466870535154840891
97209663212281002759381072062453715265566609468
【在 S********s 的大作中提到】
: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)
|
m********3
发帖数: 4806 | |
z***m
发帖数: 1602 | 26 用dp，把前面的结果存起来
coin change problem的变形
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha
【在 S********s 的大作中提到】
: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)
|
c*****m
发帖数: 271 | |
t*******e
发帖数: 274 | 28
楼主的题目是前后次序有影响，在此基础上该怎么改？
【在 z***m 的大作中提到】
: 用dp，把前面的结果存起来
: coin change problem的变形
: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha
|
z***m
发帖数: 1602 | 29 对每个case，直接乘以 n!,.
比如算出的C[1,5]为x，直接乘以2。 如果是C[1 2 5]就乘以3！
【在 t*******e 的大作中提到】
:
: 楼主的题目是前后次序有影响，在此基础上该怎么改？
|
t*******e
发帖数: 274 | 30
不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
代码你是怎么做的么
【在 z***m 的大作中提到】
: 对每个case，直接乘以 n!,.
: 比如算出的C[1,5]为x，直接乘以2。 如果是C[1 2 5]就乘以3！
|
|
|
y*********8
发帖数: 387 | |
w*******i
发帖数: 186 | 32 感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个Set
Long>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
列数目，然后在set里求和。
另外dp表可以用长度为50的滚动数组，减少内存开销。 |
p**t
发帖数: 157 | 33 已知组合数 求排列数不需要具体列出来所有的排列吧。。。
【在 w*******i 的大作中提到】
: 感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个Set: Long>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
: 列数目，然后在set里求和。
: 另外dp表可以用长度为50的滚动数组，减少内存开销。
|
z***m
发帖数: 1602 | 34 找unique的元素个数，设为n，然后乘以n！
【在 t*******e 的大作中提到】
:
: 不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
: 代码你是怎么做的么
|
y*****h
发帖数: 22 | 35 这样可以不可以？
public long tellMoneyCombinations(int money) {
long[] f = new long[money+1];
f[0] = f[1] = 1;
for(int i=2; i<=money; i++) {
f[i] = f[i-1];
if(i>=5) f[i]+=f[i-5];
if(i>=20) f[i]+=f[i-20];
if(i>=50) f[i]+=f[i-50];
}
return f[money];
} |
s*******z
发帖数: 14 | 36 动态规划。
问下楼主，我怎么没看到有准备材料？就是HR邮件里面那一堆么？ |
s*******z
发帖数: 14 | 37 这样不可以。有重复的
【在 y*****h 的大作中提到】
: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }
|
t*****a
发帖数: 106 | 38 这个是对的
【在 y*****h 的大作中提到】
: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }
|
t*****a
发帖数: 106 | 39 题目就是要有重复的。
【在 s*******z 的大作中提到】
: 这样不可以。有重复的
|
x*******9
发帖数: 138 | 40 一般情况下，在OJ上，这种DP题都是让你MOD一个大质数的。
所以不用太担心溢出。
gl, hf |
|
|
l***4
发帖数: 1788 | 41 public static long atm(int x) {
long[] arr = new long[x+1];
Arrays.fill(arr, -1);
return helper(arr, x);
}
private static long helper(long[] arr, int x) {
if (x < 0) {
return 0;
}
if (x == 0) {
return 1;
}
if (arr[x] < 0) {
arr[x] = helper(arr, x-1) + helper(arr, x-5) + helper(arr, x-20)
+ helper(arr, x-50);
}
return arr[x];
} |
s********l
发帖数: 998 | 42 我也好奇
哪里给的或者找到的facebook复习材料啊？ |
