题解 | #走方格的方案数#

n行m列的格子正好有(n+1)(m+1)个终点，dp[n][m]正好表示到达n行m列格子终点的路径数，最左和最上边缘线上的实际不会作为终点的点可用于边界值初始化，因为每个边缘只有一个唯一可能的方向到达边缘上的点，使用路径数都为1，对于其他终点，每个终点只有可能从左边或者上边的终点到达。

import java.util.Scanner

fun main(args: Array<String>) {
    val read = Scanner(System.`in`)
    val res = read.nextLine().split(' ').map {
        it.toInt()
    }
    val h = res[0]
    val v = res[1]
    val dp = Array(h + 1) {index1->
        Array(v + 1) {
            if (index1 == 0 || it== 0) 1 else 0
        }
    }

    for (i in 1 ..h) {
        for (j in 1 .. v) {
            dp[i][j] = dp [i-1][j] + dp[i][j-1]
        }
    }
    println(dp[h][v])
}

空间压缩：

因为每一个dp[i][j]只与前一个dp值或上一个dp值相关，所以可以采用大小为列数m+1的一维数组循环写入m次得到最终dp值，初始化为全为1，从左到右遍历

import java.util.Scanner

fun main(args: Array<String>) {
    val read = Scanner(System.`in`)
    val res = read.nextLine().split(' ').map {
        it.toInt()
    }
    val h = res[0]
    val v = res[1]
    val dp = Array(v + 1) {
            1
        }

    for (i in 1 ..h) {
        for (j in 1 .. v) {
            dp[j] = dp [j-1]+ dp[j]
        }
    }
    println(dp[v])
}