无法将此递归代码记忆到自上而下的DP

发布于 2025-01-19 07:09:17 字数 1880 浏览 4 评论 0原文

我在一个测试中遇到了这个问题。我为此写了一个递归解决方案（我在一些测试用例上尝试了它，似乎工作正常）。我正在尝试记住此代码，但无法做到这一点。

问题陈述是这样的，

您在IPL11应用程序上玩幻想板球。该游戏与其他幻想板球应用有些不同。在这里，您将获得两个播放器列表。这两个列表都包含n每个玩家。列表根据它们提供的价值表示。

您需要从这些2*n玩家中精确选择n播放器。

选择需要根据以下规则进行。

您可以从list1的末尾选择list2的末尾，
一旦选择了一个播放器，就将他从该列表中删除。
为了获得更好的玩家，您还可以选择丢弃玩家并删除他们从列表的末尾。您最多可以在K次进行丢弃操作。

自然，您希望在团队中获得最大价值。根据上述规则从两个列表中选择n播放器后，找到您可以获得的最大值。

示例

n: 6
list1: [10, 13, 31, 12, 12, 18]
list2: [34, 12, 3, 23, 11, 13]
k: 2

O/P: 112

Explanation:

* Select 18 (list1)
* Select 13 (list2)
* Skip 11 (list2)
* Select 23 (list2)
* Select 12 (list1)
* Skip 3 (list2)
* Select 12 (list2)
* Select 34 (list2)

我的递归解决方案，

public static int helper(int[] list1, int[] list2, int n1, int n2, int k, int count) {
        if(count == n) return 0;
        int chooseFromList1 = Integer.MIN_VALUE;
        int chooseFromList2 = Integer.MIN_VALUE;
        if(n1 > 0) {
            chooseFromList1 = list1[n1-1]+helper(list1, list2, n1-1, n2, k, count+1);
        }
        if(n2 > 0) {
            chooseFromList2 = list2[n2-1]+helper(list1, list2, n1, n2-1, k, count+1);
        }
        int temp = Integer.MIN_VALUE;
        if(k > 0) {
            int skipList1 = helper(list1, list2, n1-1, n2, k-1, count);
            int skipList2 = helper(list1, list2, n1, n2-1, k-1, count);
            temp = Math.max(skipList1, skipList2);
        }
        return Math.max(Math.max(chooseFromList1, chooseFromList2), temp);
    }

我所做的是，我在此递归代码中采取了4个选择，

如果N1＆gt; 0
如果n2＆gt; 0
如果k＆gt; 0
从list2跳过最后一个元素，如果k＆gt; 0

我想将其转换为自上而下的DP，但无法为其编写代码。

原文

I got this problem on one of my tests. I wrote a Recursive solution for it (I tried it on a few test cases, it seems to be working fine). I am trying to memoize this code, but am not able to do that.

The problem statement goes like this,

You are playing Fantasy Cricket on IPL11 App. The game is a bit different from other Fantasy Cricket Apps.
Here you are given two lists of players. Both lists contain n players each.
The list is denoted based on the value they provide.

You need to select exactly n players out of these 2*n players.

The selection needs to be done based on the following rules.

You can select either from the end of list1 or end of list2
Once you select a player, he is removed from that list.
To get access to better players, you also have an option to discard a player and remove them
from the end of the list. You can do the discard operation at most k times.

Naturally, you would want to get the maximum value possible in your team. Find the maximum value that you can get after selecting n players from the 2 lists based on the above rules.

Example

n: 6
list1: [10, 13, 31, 12, 12, 18]
list2: [34, 12, 3, 23, 11, 13]
k: 2

O/P: 112

Explanation:

* Select 18 (list1)
* Select 13 (list2)
* Skip 11 (list2)
* Select 23 (list2)
* Select 12 (list1)
* Skip 3 (list2)
* Select 12 (list2)
* Select 34 (list2)

My Recursive Solution,

public static int helper(int[] list1, int[] list2, int n1, int n2, int k, int count) {
        if(count == n) return 0;
        int chooseFromList1 = Integer.MIN_VALUE;
        int chooseFromList2 = Integer.MIN_VALUE;
        if(n1 > 0) {
            chooseFromList1 = list1[n1-1]+helper(list1, list2, n1-1, n2, k, count+1);
        }
        if(n2 > 0) {
            chooseFromList2 = list2[n2-1]+helper(list1, list2, n1, n2-1, k, count+1);
        }
        int temp = Integer.MIN_VALUE;
        if(k > 0) {
            int skipList1 = helper(list1, list2, n1-1, n2, k-1, count);
            int skipList2 = helper(list1, list2, n1, n2-1, k-1, count);
            temp = Math.max(skipList1, skipList2);
        }
        return Math.max(Math.max(chooseFromList1, chooseFromList2), temp);
    }

What I did is, I took 4 choices in this recursive code,