在不超过总和 K 的情况下，可以从两个堆栈顶部移除的最大块数

Question

给定两堆非负整数。计算在不超过总和 K 的情况下可以从堆栈顶部移除的最大整数数。假设给出两个堆栈 A 和 B，如下图所示。然后最多可以删除 4 个整数，如第二张图片所示，而不超过总和 10。如果需要，请在此处找到 source。

我尝试了DP方法来解决问题。但是我只能通过几个测试用例。谁能告诉我哪里出了问题。

static int maxStacks(int maxSum, int[] a, int[] b) {
    Stack<Integer> stackA = new Stack<>();
    Stack<Integer> stackB = new Stack<>();
    for(int i=a.length-1;i>=0;i--) {
        stackA.push(a[i]);
    }
    for(int i=b.length-1;i>=0;i--) {
        stackB.push(b[i]);
    }
    return solve(stackA, stackB, maxSum, 0);
}

static int solve(Stack<Integer> a, Stack<Integer> b, int maxSum, int currSum) {
    if(a.isEmpty() && b.isEmpty()) {
        return 0;
    }
    int ansA;
    if(a.isEmpty()) {
        ansA = 0;
    } else {
        int peek = a.peek();
        if((currSum + peek) > maxSum) {
            ansA = 0;
        } else {
            a.pop();
            ansA = 1 + solve(a, b, maxSum, (currSum + peek));
        }
    }
    int ansB;
    if(b.isEmpty()) {
        ansB = 0;
    } else {
        int peek = b.peek();
        if((currSum + peek) > maxSum) {
            ansB = 0;
        } else {
            b.pop();
            ansB = 1 + solve(a, b, maxSum, (currSum + peek));
        }
    }
    return Math.max(ansA, ansB);
}

Answer 1

我认为您算法中的核心问题来自 Stack 的浅拷贝。在以下代码段中：

        } else {
            a.pop();
            ansA = 1 + solve(a, b, maxSum, (currSum + peek));
        }

您已经从堆栈 A 弹出，因此当 B 的流程在 ansB = 1 + solve(a, b, maxSum, (currSum + peek)); 执行时，您实际上传递的不是原始堆栈 A，而是修改后的堆栈。

另外，我认为这不是 DP 解决方案。我建议您阅读更多相关内容。

在不超过总和 K 的情况下，可以从两个堆栈顶部移除的最大块数

Maximum number of blocks that can be removed from top of two stacks without exceeding the sum K

java

stack

data-structures