Google Interview - Max Coins

http://www.1point3acres.com/bbs/thread-147256-1-1.html
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

stack 是说要先取出上面的coin，之后才能拿下面的。 题意大概就是有k堆coin，拿n个，但是是最上面的n个(可以是不同堆)

用递归写了一个，不知道有没有DP的解法
看错了，是k个stack，上面的做法是2个的，k个的一样的思路
https://github.com/hejian2356/-Algorithms/blob/master/GetMaxSumFromTwoStack.java
public static int findMaxSum(List<Stack<Integer>> stacks,int n){
                if(n == 0){
                        return 0;
                }
                int length = stacks.size();
                int res = Integer.MIN_VALUE;
                for(int i=0;i<length;i++){
                        Stack<Integer> cur = stacks.get(i);
                        if(!cur.isEmpty()){
                                int temp = cur.pop();
                                int sum = temp + findMaxSum(stacks,n-1); // need cache
                                if(sum > res){
                                        res = sum;
                                }
                                cur.push(temp);
                        }
                }
                return res;
        }

public int getmaxsum(int[][] nums, int n) {
int[][] dp = new int[nums.length+1][n+1];
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= nums.length; i++) {
int len = nums[i-1].length, sum = 0;
for (int j = 0; j < len && j < k; j++) {
sum += nums[i-1][j];
dp[i][k] = Math.max(dp[i][k], sum+dp[i-1][k-j-1]);
}
}
}
return dp[nums.length][n];
}
     

//dp
public int getMax(int n) {
int[] nums1 = {1, 4, 700, 3}, nums2 = {5, 10, 6};
int len1 = nums1.length, len2 = nums2.length;
int[][][] dp = new int[len1+1][len2+1][n];
int sum1 = 0, sum2 = 0;
for (int i = 0; i < len2; i++) {
int sum = 0;
for (int k = 0; k < n; k++) {
if (i+k >= len2) {
break;
}
sum += nums2[i+k];
dp[len1][i][k] = sum;
}
}
for (int j = 0; j < len1; j++) {
int sum = 0;
for (int k = 0; k < n; k++) {
if (j+k >= len1) {
break;
}
sum += nums1[j+k];
dp[j][len2][k] = sum;
}
}

for (int k = 0; k < n; k++) {
for (int j = 0; j < len1; j++) {
for (int i = 0; i < len2; i++) {
if (k == 0) {
dp[j][i][k] = Math.max(nums1[j], nums2[i]);
}
else {
dp[j][i][k] = Math.max(nums1[j]+dp[j+1][i][k-1], nums2[i]+dp[j][i+1][k-1]);
}
}
}
}
return dp[0][0][n-1];
}
//recursion
private int helper(int[] nums1, int[] nums2, int sta1, int sta2, int n) {
int sum = 0;
if (sta1 == nums1.length) {
for (int i = sta2; i < sta2+n; i++) {
if (i == nums2.length) {
return -1;
}
sum += nums2[i];
}
return sum;
}
if (sta2 == nums2.length) {
for (int i = sta1; i < sta1+n; i++) {
if (i == nums1.length) {
return -1;
}
sum += nums1[i];
}
return sum;
}
if (n == 1) {
return Math.max(nums1[sta1], nums2[sta2]);
}
return Math.max(nums1[sta1]+getmax(nums1, nums2, sta1+1, sta2, n-1), nums2[sta2]+getmax(nums1, nums2, sta1, sta2+1, n-1));
}

public int getMaxRecursion(int n) {
int[] nums1 = {1, 4, 700, 3}, nums2 = {5, 10, 6};
return getmax(nums1, nums2, 0, 0, n);
}
http://www.1point3acres.com/bbs/thread-147244-1-1.html

public int getMax(int n) {

                int[] nums1 = {1, 4, 700, 3}, nums2 = {5, 10, 6};

                int len1 = nums1.length, len2 = nums2.length;

                int[][][] dp = new int[len1+1][len2+1][n];

                for (int k = 0; k < n; k++) {

                        dp[len1][k][k] += nums2[k];

                }

                for (int k = 0; k < n; k++) {

                        dp[k][len2][k] += nums1[k];

                }

                for (int k = 0; k < n; k++) {

                        for (int j = 0; j < len1; j++) {

                                for (int i = 0; i < len2; i++) {

                                        if (k == 0) {

                                                dp[j][k] = Math.max(nums1[j], nums2);

                                        }

                                        else {

                                                dp[j][k] = Math.max(nums1[j]+dp[j+1][k-1], nums2+dp[j][i+1][k-1]);

                                        }-google 1point3acres

                                }

                        }

                }

                return dp[0][0][n-1];

        }

http://www.1point3acres.com/bbs/thread-147244-2-1.html
int getMaxSum(vector<vector<int>> &sum, int n) {
    int k = sum.size();
    vector<vector<int>> dp(k, vector<int>(n + 1,0));
    for(int i = 1; i <= sum[0].size(); i++) {
        dp[0][i] = sum[0][i-1];
    }
    for(int i = 1; i < k; i++) {
        for(int j = 0; j <= n; j++) {
            if(j == 0) {
                dp[i][j] = 0;
            } else {
                int l1 = sum[i-1].size();
                int l2 = sum[i].size();
                for(int m = max(0, j-l1); m <= min(j, l2); m++) {
                    dp[i][j] = max(dp[i][j],(m == 0 ? 0 : sum[i][m-1]) + dp[i-1][j-m]);
                }
            }
        }
        return dp[k-1][n];
    }
}