Участник:Hellhoundmipt/build-array-where-you-can-find-the-maximum-exactly-k-comparisons

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

https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/submissions/

Scala код

object Solution {
    val MOD = 1000000007
    def numOfArrays(n: Int, m: Int, k: Int): Int = {
        val dp = Array.fill[Long](n+1, m+1, k+1)(0)
        for (i <- 1 to m) dp(1)(i)(1) = 1
        for {
            i <- 1 to n
            j <- 1 to m
            k <- 1 to k
        } {
            val start = (j * dp(i - 1)(j)(k)) % MOD
            val s = (1L until j).fold(start){ case (acc, x) => (acc + dp(i - 1)(x.toInt)(k - 1)) % MOD }
            dp(i)(j)(k) += s
        }
        (1L to m).fold(0L){ case (acc, i) => (acc + dp(n)(i.toInt)(k)) % MOD }.toInt
    }
}