百度笔试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 北京

相关推荐

05-28 23:26
河南大学 Java
双非本,刚学完Redis,项目只有外卖和点评,八股没准备,算法只有lqb省一,感觉敲的项目也是一言难尽没怎么吸收。怎么你们都有实习了
大牛之途:27急个锤子,你投日常实习最好的时间就是9,10月份,那时候暑期实习都结束了,正是缺人的时候。这份日常又能给你的暑期实习增加竞争力,暑期找的好了秋招也不怕了,都是环环相扣的
点赞 评论 收藏
分享
05-07 19:10
已编辑
中国科学技术大学 C++
silly01:现在先去 momenta,8-9月去鹅找日常实习,八股文算法背好了你这随便进。不过建议补充一下后端知识,MySQL、Redis看下八股,再补个6824,加点go后台的技术栈,9月随便进大厂。CPP后端只能来WXG
点赞 评论 收藏
分享
05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务