Участник:Hellhoundmipt/stone-game-ii

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/stone-game-ii/

Scala код

object Solution {
    import scala.math.{max, min}
    var cache = Array.fill(100, 100)(0)
    def stoneGameII(piles: Array[Int]): Int = {
        val n = piles.length
        for (i <- n - 2 to 0 by -1) piles(i) += piles(i + 1)
        var res = dp(0, 1, n, piles.toSeq)
        cache = Array.fill(100, 100)(0)
        res
    }
 
    def dp(i: Int, m: Int, n: Int, summedPiles: Seq[Int]): Int = {
        if (2 * m + i >= n) summedPiles(i)
        else if (cache(i)(m) > 0) cache(i)(m)
        else {
            cache(i)(m) = (for (x <- 1 to 2 * m) yield summedPiles(i) - dp(x + i, max(x, m), n, summedPiles)).max
            cache(i)(m)
        }
    }
}