石子问题

func stoneGame(piles []int) bool {
dp := make([][]int, len(piles))
for i := 0; i < len(dp); i++ {
dp[i] = make([]int, len(piles))
}

for size := 1; size <= len(dp); size++ {
    // size表示剩下多少,最少剩下一个
    for i := 0; i + size - 1 < len(dp); i++ {
        j := i + size - 1

        if i == j {
            dp[i][j] = piles[i] // init
            continue
        }

        priority := (len(piles) - size) % 2 

        // 开始有的减去现在的
        if priority == 0 {
            dp[i][j] = max(piles[i] + dp[i + 1][j], piles[j] + dp[i][j - 1])
        } else {
            dp[i][j] = min(piles[i] + dp[i + 1][j], piles[j] + dp[i][j - 1])
        }
    }
}
return dp[0][len(piles) - 1] >= 0

}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。