Max sum of n coins

Given k stack of coins, take n conins, what is the max sum of the n coins.
eg. stack1: 1, 4, 700, 3
stack2: 5, 10, 6
if n = 2, then the max sum should be 5+10
if n = 3, then the max sum should be 1+4+700

Discussion

递归的思想：给定一个stack，弹出一个元素，在该剩下的元素和其他stack中找出来n-1个coins使其和最大，加上弹出的元素，决定要不要update result。
注意：在处理下一个stack之前要把该元素push进去，不然下一个stack的时候就取不到这个元素了。

Solution

k=2的情况：

 int findMaxSum(stack<int> stack1, stack<int> stack2, int n){
     if (n == 0){//递归终止条件
        return 0;
    }
    int res = 0;
    if (!stack1.empty()){
        int temp = stack1.top();
        stack1.pop();//弹出元素
        int sum_left = findMaxSum(stack1, stack2, n - 1);//剩余n-1个coin的最大值
        int sum = temp + sum_left;
        if (res < sum){//决定是否要update result
            res = sum;
        }
        stack1.push(temp);//把该元素放回去
    }
    if (!stack2.empty()){//接着处理下一个栈
        int temp = stack2.top();
        stack2.pop();
        int sum_left = findMaxSum(stack1, stack2, n - 1);
        int sum = temp + sum_left;
        if (res < sum){
            res = sum;
        }
        stack2.push(temp);
    }
    return res;
}

k>2的情况也类似：

int FindMaxSum(vector<stack<int> > stacks, int n) {
     if (n == 0) 
         return 0;
     int result = INT_MIN;
     for (int i = 0; i < stacks.size(); i++) {
         //stack<int> cur = stacks[i];
         while (stacks[i].empty() == false) {
             int tmp = stacks[i].top();
             stacks[i].pop();
             int sum = tmp + FindMaxSum(stacks, n - 1);
             if (sum > result) {
                 result = sum;
             }
             stacks[i].push(tmp);
         }
     }
     return result;
 }

这个题再往深处想就成了将整数n拆分成k个整数的问题了，等价于将n个相同的球放入k个不同的盒子里的问题，总共有C(n+k-1, k-1)中放法。

为什么这么说呢，以k=2为例，stack1和stack2中分别求出前i个coin的累积和，i=0~n。这个问题就成了在第一个stack中取前i个，则第二个stack中取n-i个。即将n拆分成2个整数的问题，有n+1中拆分方法。