Unique Paths
MediumDynamic Programming
The problem
Count the number of paths from the top-left to the bottom-right of an m x n grid, moving only right or down. One-row DP.
Sample input
m = 3, n = 7Sample output
28Show the solution · 8 languages
fun uniquePaths(m: Int, n: Int): Int {
val dp = IntArray(n) { 1 }
for (i in 1 until m) {
for (j in 1 until n) {
dp[j] += dp[j - 1]
}
}
return dp[n - 1]
}
fun main() {
println(uniquePaths(3, 7))
}