百度笔试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秋招笔试心得体会#