百度笔试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;
}