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

走方格的方案数

https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b

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])
}

全部评论
娟疯嘞娟疯嘞,大半夜三点写题解,疯嘞疯嘞
点赞 回复 分享
发布于 2024-02-27 04:07 河南

相关推荐

小叮当411:应该是1-3个月吧
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
怎么起名字:早知道就不读书了,害得我送外卖还得扶眼镜
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务