google 面试一道 求大神帮忙解解

sxh53 发表于 2015-11-10 02:27
一个简单解法是：
假设我从stack1里面取A个数 stack2里取B个数。 A+B=n 求怎么去解这个A和B。
再仔细想， ...

对于k stack，按照答主的思路的话应该就是讲n拆分成k个整数的问题了吧，等价于将n个相同的球放入k个不同的盒子的问题，总共有C(n+k-1, k-1)中方法。具体怎么做请大神支招

宝贝忆彼岸 发表于 2015-11-10 02:17
public  int findMaxSum(Stack stack1,Stack stack2,int n){
                if(n == 0 || (stac ...

你这是从stack1取一个，然后从stack2取下一个吧？楼主取的N个是不是都必须出自同一个stack？而且是stack顶部？

DP吧
dp(k,i) = 前k个stack,一共取i个coin得到的最大值。

1. dp(k,i) =max( dp(k-1,i),dp(k-1,i-1)+sum(k,1),dp(k-1,i-2)+sum(k,2)...)

复制代码