百度笔试9.20矩阵路径数目代码

用两个二维数组分别记录从左往右的前缀和,以及从上到下的前缀和,由此优化时间到O(N^2)

#include <bits/stdc++.h>
using namespace std;
#define N 2005

int dp[N][N];
int rowpre[N][N];
int colpre[N][N];
const int modval = 1e9 + 7;

int main(){
    dp[1][1] = 1;
    for(int i = 1; i <= 2000; ++i){
        for(int j = 1; j <= 2000; ++j){
            dp[i][j] += rowpre[i][j - 1] + colpre[i - 1][j];
            rowpre[i][j] = (dp[i][j] + (j - 2 > 0 ? rowpre[i][j - 2] : 0)) % modval;
            colpre[i][j] = (dp[i][j] + (i - 2 > 0 ? colpre[i - 2][j] : 0)) % modval;
        }
    }
    int t;
    cin >> t;
    int m, n;
    while(t--){
        cin >> m >> n;
        cout << dp[m][n] << endl;
    }
    return 0;
}
#百度##百度笔试##百度2023秋招笔试心得体会#
全部评论
hi~同学,秋招遇“寒气”,牛客送温暖啦!23届秋招笔面经有奖征集中,参与就得牛客会员7天免费体验,最高赢300元京东卡!戳我去看>>>https://www.nowcoder.com/link/zhengjipinglun
点赞 回复 分享
发布于 2022-09-22 10:27 北京
他说的走奇数步,如果1直接走到3,5,7,9步到下一个点这个还成立嘛,感觉这个是考虑每次走1步或者3步的情况
点赞 回复 分享
发布于 2022-09-21 19:33 黑龙江
能ac吗
点赞 回复 分享
发布于 2022-09-21 16:31 北京

相关推荐

昨天 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

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