[Scala] Clean Functional DP
Let dp[i][j] be the number of permutations that s[i:] could form with the first number be the jth smallest candidate number.\n\nThen if s[i] == \'D\', because f
Let `dp[i][j]` be the number of permutations that `s[i:]` could form with the first number be the `j`th smallest candidate number.\n\nThen if `s[i] == \'D\'`, because for `dp[i][j]` we already choose the `j`th smallest possible value, we can only choose the candidate numbers before `j` for the `i+1`th position. So `dp[i][j] = dp[i + 1][0] + dp[i + 1][1] + ... + dp[i + 1][j - 1]`.\n\nThe same logic applies to the case when `s[i] == \'I`. We can choose the `j + 1`th, `j + 2`th... candidate value for position `i + 1`.  Note that because `j`th value is taken, the `j + 1`th value in `i`\'s candidate numbers will be the `j`th value in `i+1`\'s candidate numbers. So `dp[i][j] = dp[i + 1][j] + dp[i + 1][j + 1] + ...`.\n\nBecause `dp[i][]` only depends on `dp[i + 1][]`, we can eliminate the first dimension of dp states to save some memory.\n```Scala\nobject Solution {\n  def numPermsDISequence(s: String): Int = {\n    val mod = (1e9 + 7).toInt\n    def add(x: Int, y: Int) = ((x + y) % mod + mod) % mod\n\n    s.reverse.foldLeft(Vector(1)) {\n      case (dp, \'D\') => Vector.tabulate(dp.size + 1)(j => (0 until j).map(dp).fold(0)(add))\n      case (dp, \'I\') => Vector.tabulate(dp.size + 1)(j => (j until dp.size).map(dp).fold(0)(add))\n      case _ => null\n    }.reduce(add)\n  }\n}\n```
[]