|
|---|
|
| 相关主题 |
|---|
| ● careercup上这道题我竟然没看懂 | ● stable rearrange an integer array with + and - | | ● MS a0, a1, ..., b0, b1... 问题 | ● 找2个sorted array中的第K小的元素，有O(lgn)方法吗？ | | ● Ask a amazon question from careercup. | ● 问几道算法题 | | ● a[i] + b[j] = c[k] 的题有靠谱的答案不? | ● 问一道CareerCup里的题目 | | ● 问个最近面试里的题目 | ● 问一道在sorted array里search的问题 | | ● array a1,a2,... ,an, b1,b2,..., bn | ● partition array problem | | ● 一刀题 | ● 问个题目，找不在区间内的所有数 | | ● 请教一道题目 | ● 请教一个题目 |
|
|
|
|
|
t******h
发帖数: 120 | 1 Write a function that takes in an array of integers and outputs the number
of ways you can combine those integers to obtain a sum of 15.
Example: for [10,5,3,2], output = 2.
我只想到用递归 生成所有结果
如果等于15就把计数器加一
careercup上说可以用DP来做 但是我想不到
请问这个问题用DP怎么做？ | D***h
发帖数: 183 | 2 for a given sum and array a[1],a[2]....a[n]
f(sum, i, n) = f(sum-a[i], i+1,n)+f(sum,i+1,n)
where f(sum, i,n) is the # of combination from a[i] to the end a[n].
【在 t******h 的大作中提到】
: Write a function that takes in an array of integers and outputs the number
: of ways you can combine those integers to obtain a sum of 15.
: Example: for [10,5,3,2], output = 2.
: 我只想到用递归 生成所有结果
: 如果等于15就把计数器加一
: careercup上说可以用DP来做 但是我想不到
: 请问这个问题用DP怎么做？
| m*****g
发帖数: 226 | | b********h
发帖数: 119 | 4 这个问题跟经典的knapsack问题很像。从两个维度上可以减小问题的规模；一个是sum
的大小，另一个是数组的大小。对于给定的sum和数组，可以考虑数组里的每一个元素a
[i]。要么a[i]被选中，要么不被选中。如果a[i]被选中,那么答案就是剩下的数组元素
有多少种组合能生成sum-a[i]。反之，答案就是剩下的数组元素有多少种组合能生成
sum。 | c******n
发帖数: 4965 | 5 recursion ---> memoization ---> DP
is rather simple, it's almost a mechanical translation process
your recursion version for this problem is:
let a[] be the array of possible integers
number_of_ways(N, a[]) = sum( number_of_ways(N- a[i], a[] - a[i]) )
while base case is number_of_ways(0, anything) = 1
and number_of_ways(n , anything) = 0 where n < 0
这个题如果像上面限制每个integer 只能用一次， 用DP 不太好表达 ， 如果可以重复
使用，就很
简单：
for n = 1 to 15:
for (i=1 to MAX_NUMBER_OF_AVAILABLE_INTEGERS ) :
if ( n - a[i] > 0 ) :
ways[n] += ways[n-a[i]]
【在 t******h 的大作中提到】
: Write a function that takes in an array of integers and outputs the number
: of ways you can combine those integers to obtain a sum of 15.
: Example: for [10,5,3,2], output = 2.
: 我只想到用递归 生成所有结果
: 如果等于15就把计数器加一
: careercup上说可以用DP来做 但是我想不到
: 请问这个问题用DP怎么做？
| B********n
发帖数: 384 | 6 假设数组是a[i], i = 1..n
如果某些数字的和为sum，有两种情况，或者第n个数字被选，或者第n个数字没有被选
count(n, sum) = count (n-1, sum) + count(n-1, sum-a[n]);
只要用一个二维数组来保存dp状态就可以了
【在 t******h 的大作中提到】
: Write a function that takes in an array of integers and outputs the number
: of ways you can combine those integers to obtain a sum of 15.
: Example: for [10,5,3,2], output = 2.
: 我只想到用递归 生成所有结果
: 如果等于15就把计数器加一
: careercup上说可以用DP来做 但是我想不到
: 请问这个问题用DP怎么做？
| h********e
发帖数: 1972 | 7 即便DP时间上也快不到哪里去。。没啥用。。这种题随便坐就成 |
|
|
|
|
| 相关主题 |
|---|
| ● 请教一个题目 | ● 问个最近面试里的题目 | | ● Google电话面试题目 | ● array a1,a2,... ,an, b1,b2,..., bn | | ● G题一道（1） | ● 一刀题 | | ● Careercup question. | ● 请教一道题目 | | ● careercup上这道题我竟然没看懂 | ● stable rearrange an integer array with + and - | | ● MS a0, a1, ..., b0, b1... 问题 | ● 找2个sorted array中的第K小的元素，有O(lgn)方法吗？ | | ● Ask a amazon question from careercup. | ● 问几道算法题 | | ● a[i] + b[j] = c[k] 的题有靠谱的答案不? | ● 问一道CareerCup里的题目 |
|
|
|
