在本章中，我们将解决如何在DP的帮助下获得游戏中最大硬币的问题。
问题陈述：
您和您的朋友正在玩游戏，以从偶数长度的数组中选择数字。您需要找到一种解决方案，以便可以选择最大金额，然后赢得比赛。
示例数组
您是玩家P1，您的朋友是玩家P2。
最初，您选择1
您的朋友选择2
你选1
您的朋友选择4
您的总数= 2
您的朋友总数= 6
因此，在这里您需要提出一个将成为赢家的策略。我们可以通过DP解决此问题。
考虑数组：
最初，下面将是我们的DP阵列：
因为我们有4个元素，所以我们采用4 x 4矩阵。让我们开始填充矩阵。我们将在[0,3]索引处获得结果。
因为有2个玩家，我们表示为[4，5]。此处，玩家1的获利4和玩家5的获利5。这意味着，玩家1的获利为1。 ST 元素，而玩家2的利润将是2 nd 元件。
因此，最初我们只有1个元素，即4，其索引为0。
因此，如果您只有'4'，则将选择'4'，播放器2将选择0。由于只有1个元素，而播放器1已选择它，播放器2将得到0。因此我们可以将DP数组填充为dp [0,0] = [4,0]。
同样，如果您只有8 dp [1，1] = [8，0]
同样，如果您只有1 dp [2，2] = [1，0]
同样，如果您只有2 dp [3，3] = [2，0]
更新后的DP表将为
现在让我们在t时间取2个元素并进行计算。
首先，您有[4，8]。因此玩家P1将选择8，而玩家2将选择4。因此dp [0，1] = [8，4]。
接下来，您有[8，1]。这里P1 = 8，P2 = 1。
因此，dp [1，2] = [8，1]。
接下来，您有[1，2]。这里P1 = 2，P2 = 1。
因此，dp [2，3] = [2，1]。
因此，我们最终的DP数组将为：
从上面我们可以得出DP公式吗？是的，我们可以得出。
好吧，集中在下面：
对于索引dp [0，1]，我们有元素[4，8]。如果玩家P1选择4，那么玩家P2选择8，那么玩家P1将不得不再次选择玩家P2之后剩下的。
最初，P1选择了4m P2选择了8。由于玩家P2选择了8，并且索引为1，因此您需要检查2 nd dp [1，1]中的值。 2 nd 值，即P2的值为0。您添加了选择的值，即4 + 0 = 4。
同样，如果您在[4，8]中选择8，P2将选择4。您需要检查2 nd 索引[0，0]的值为0，即0。您将选择的值添加为8 + 0 =8。现在您有2个值[4，8]。您需要取值的最大值，即8。因此我们得到[8，4]。
接下来，我们将选择3个元素[4、8、1]，索引为[0、1、2]，并使用与上述相同的方法求解。
因此，首先P1选择4，然后我们需要添加2 nd 索引[1,2]处的值，即4 +1 = 5。
否则P1选择1，那么我们需要加2 nd 索引[0，1]的值，即1 + 4 =5。无论如何，我们选择5。
并且P2将选择8。因此，对于dp [0，2] = [5，8]
现在我们将选择[8，1，2]
如果P1选择8，我们需要加2 nd 值[2，3]。
8 +1 = 9
如果P1选择2，我们需要加上2 nd 值[1，2]。
2 +1 = 3
由于[9，3]的最大值为9。P1将选择9。P2将采用我们选择的下一个值。即P2将花费1。
因此，dp [1，3] = [9，1]。
现在我们一次要考虑四个要素。
[4、8、1、2]和索引为[0、1、2、3]。
如果P1选择4，那么我们需要加2 nd 元素位于索引[1，3]。
即4 +1 = 5。
如果P1选择2，那么我们需要加2 nd 索引为[0，2]的元素。
即2 + 8 = 10。
我们将选择10，因为它是最大值，而2 nd 玩家获得4 +1 = 5。
因此最终dp [0，3] = [10，5]。
因此，结果。
C ++解决方案
#include <iostream>
using namespace ST d;
int get_max_coin(int* arr, int n)
{
int dp_table[n][n];
for (int gap = 0; gap < n; ++gap)
{
for (int i = 0, j = gap; j < n; ++i, ++j)
{
int x = 0;
if(((i + 2) <= j))
{
x = dp_table[i + 2][j];
}
int y = 0;
if((i + 1) <= (j - 1))
{
y = dp_table[i + 1][j - 1];
}
int z = 0;
if((i <= (j - 2)))
{
z = dp_table[i][j - 2];
}
dp_table[i][j] = max(
arr[i] + min(x, y),
arr[j] + min(y, z));
}
}
return dp_table[0][n - 1];
}
int main()
{
int arr1[] = { 4, 8, 1, 2};
int n = sizeof(arr1) / sizeof(arr1[0]);
cout<<"Ans : " <<get_max_coin(arr1, n)<<endl;
return 0;
}
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
