[硬币博弈]两个聪明人从两边拿硬币,最后谁会赢,递归到动态规划

快来打我* 2024-03-26 18:26 50阅读 0赞

[原题链接][Link 1]

[原题视频(左神)][Link 2]

### 递归 ###

本题有两种情况

第一种:从剩余的硬币中先手拿硬币

第二种:从剩余的硬币中后手拿硬币

先讨论第一种:

当只剩余一个硬币时,即left==right的时候,先手只能拿这一个硬币

当有多个硬币时,我们要拿的是max(拿左边的,拿右边的)

第二种情况:

当只剩余一个硬币时,我们是后手,因此拿不到硬币

当有多个硬币时,我们只能拿到min(对方拿左边的,对方拿右边的)

因为双方都是最聪明的,因此对方一定会返回让自己更小的情况

因此递归函数就可以写成下面这样

//先手函数
    public static int first(int left, int right) {
            // 先手
            if (left == right) {
                return array[left];
            } else {
                int a = second(left + 1, right) + array[left];
                int b = second(left, right - 1) + array[right];
                // 想要的是后手的最大的
                return Math.max(a, b);
            }
        }
    //后手函数
    public static int second(int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int a = first(left + 1, right);
            int b = first(left, right - 1);
            // 因为自己不能选,只能对方选,因此对方一定会返回给自己更小的数
    
            return Math.min(a, b);
            }
        }

从递归到动态规划

让我们观察两个参数,left,right,当left和right固定的时候,函数结果也就随之固定

并且函数结束的条件是当left == right的时候

先手函数返回的是最后一个硬币的值

后手函数返回的是0

因此我们画出下面的表格

以 array = \{2,3,4,5\}为例

**first表** right

**secon表** right

### 问题如何划分为子问题 ###

然后我们分析递归发现某个表的某个位置是由另一张表的左边那个位置和下面那个位置决定

左边位置格子 下边位置格子

即fisrt\[left\]\[right\] = max(second\[left-1\]\[right\] +array\[left\] ,second\[left\]\[right-1\] + array\[right\])

second\[left\]\[right\] = min(first\[left-1\]\[right\],first\[left\]\[right-1\])

因此我们得到下面的表

以 array = \{2,3,4,5\}为例

**first表** right

**secon表** right

### 完整代码 ###

import java.util.Scanner;
 
 public class ABtakeCoins {
 public static Scanner sc = new Scanner(System.in);
 public static int N;
 public static int array[];
 public static int dpfirst[][];
 public static int dpsecond[][];
 
 public static int first(int left, int right) {
 // 先手
 if (left == right) {
 return array[left];
 } else {
 int a = second(left + 1, right) + array[left];
 int b = second(left, right - 1) + array[right];
 // 想要的是后手的最大的
 return Math.max(a, b);
 }
 }
 
 public static int second(int left, int right) {
 if (left == right) {
 return 0;
 } else {
 int a = first(left + 1, right);
 int b = first(left, right - 1);
 // 因为自己不能选,只能对方选,因此对方一定会返回给自己更小的数
 
 return Math.min(a, b);
 }
 }
 
 public static int getWinValue(int[] arr) {
 array = arr;
 N = arr.length;
 dpfirst = new int[N][N];
 dpsecond = new int[N][N];
 for (int left = 0; left < N; left++) {
 for (int right = 0; right < N; right++) {
 dpfirst[left][right] = -1;
 dpsecond[left][right] = -1;
 }
 }
 for (int i = 0; i < N; i++) {
 dpfirst[i][i] = array[i];
 dpsecond[i][i] = 0;
 }
 int count = 1;
 while (count < N) {
 for (int i = 0; i < N - count; i++) {
 int left = i;
 int right = i + count;
 int a = dpsecond[left + 1][right] + array[left];
 int b = dpsecond[left][right - 1] + array[right];
 dpfirst[left][right] = Math.max(a, b);
 dpsecond[left][right] = Math.min(dpfirst[left + 1][right], dpfirst[left][right - 1]);
 }
 count++;
 }
 return Math.max(dpfirst[0][N - 1], dpsecond[0][N - 1]);
 }
 public static void main(String[] args) { 
 }
 }

[Link 1]: https://www.nowcoder.com/questionTerminal/3e6310ec9fb6445c814d4e0e21692f04?toCommentId=15407392
[Link 2]: https://www.bilibili.com/video/BV13g41157hK?p=19&vd_source=8651deb552ff255ac3dc29dc9a2f40ec