2021-02-15：给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿。但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

2021-02-15：给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿。但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

福哥答案2021-02-15：
这道题直接背，用自然智慧很难想到，平时需要锻炼敏感度。
1.递归。有代码。
先手 依赖 后手递归加数组元素的最大值。
后手 依赖 先手递归的最小值。
为了方便记忆，先手选大的，后手被迫选小的。实际上，先手和后手都是尽自己的努力选大的。这表面上看起来是违背了自然智慧的。
2.动态规划。有代码。
先手dp依赖【后手左】和【后手下】。
后手dp依赖【先手左】和【先手下】。

代码用golang编写，代码如下：

package main

import "fmt"

func main() {

    ret := win1([]int{5, 7, 4, 5, 8, 1})

    fmt.Println("1.递归：", ret)

    ret = win2([]int{5, 7, 4, 5, 8, 1})

    fmt.Println("2.动态规划：", ret)

}

// 根据规则，返回获胜者的分数

func win1(arr []int) int {

    if len(arr) == 0 {

        return 0

    }

    first := f1(arr, 0, len(arr)-1)

    second := g1(arr, 0, len(arr)-1)

    return getMax(first, second)

}

// arr[L..R]，先手获得的最好分数返回

func f1(arr []int, L int, R int) int {

    if L == R {

        return arr[L]

    }

    p1 := arr[L] + g1(arr, L+1, R)

    p2 := arr[R] + g1(arr, L, R-1)

    return getMax(p1, p2)

}

// // arr[L..R]，后手获得的最好分数返回

func g1(arr []int, L int, R int) int {

    //if L == R {

    //  return arr[L]

    //}

    //p1 := arr[L] + f1(arr, L+1, R)

    //p2 := arr[R] + f1(arr, L, R-1)

    //return getMin(p1, p2)

    if L == R {

        return 0

    }

    p1 := f1(arr, L+1, R) // 对手拿走了L位置的数

    p2 := f1(arr, L, R-1) // 对手拿走了R位置的数

    return getMin(p1, p2)

}

func win2(arr []int) int {

    if len(arr) == 0 {

        return 0

    }

    N := len(arr)

    fmap := make([][]int, N)

    gmap := make([][]int, N)

    for i := 0; i < N; i++ {

        fmap[i] = make([]int, N)

        gmap[i] = make([]int, N)

    }

    for i := 0; i < N; i++ {

        fmap[i][i] = arr[i]

    }

    for startCol := 1; startCol < N; startCol++ {

        L := 0

        R := startCol

        for R < N {

            fmap[L][R] = getMax(arr[L]+gmap[L+1][R], arr[R]+gmap[L][R-1])

            gmap[L][R] = getMin(fmap[L+1][R], fmap[L][R-1])

            L++

            R++

        }

    }

    return getMax(fmap[0][N-1], gmap[0][N-1])

}

func getMax(a int, b int) int {

    if a > b {

        return a

    } else {

        return b

    }

}

func getMin(a int, b int) int {

    if a < b {

        return a

    } else {

        return b

    }

}

执行结果如下：

***
[左神java代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class18/Code02_CardsInLine.java)
[评论](https://user.qzone.qq.com/3182319461/blog/1613344101)

2021-02-15：给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿。但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。的相关教程结束。