题目描述
blablabla
样例
class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& board) {
int n = board.size(), m = board[0].size();
int maxv[n+1][m+1];long long cnt[n+1][m+1];
const int MOD = 1e9+7;
memset(maxv,0xcf,sizeof maxv),memset(cnt,0,sizeof cnt);
maxv[0][0] = 0,cnt[0][0] = 1;
int nx[3] = {-1,0,-1},ny[3]={-1,-1,0};
for(int i = 1 ;i <= n ;i ++){
for(int j = 1 ;j <= m ;j ++){
if(board[i-1][j-1] == 'X') continue;
int t = isdigit(board[i-1][j-1]) ? board[i-1][j-1]-'0':0;
for(int k = 0 ; k < 3 ;k ++){
if(maxv[i][j] < maxv[i+nx[k]][j+ny[k]]+t){
maxv[i][j] = maxv[i+nx[k]][j+ny[k]]+t ;
cnt[i][j] = cnt[i+nx[k]][j+ny[k]];
}else if(maxv[i][j] == maxv[i+nx[k]][j+ny[k]]+t){
cnt[i][j] =(cnt[i][j] + cnt[i+nx[k]][j+ny[k]])%MOD;
}
}
}
}
return {max(maxv[n][m],0),(int)cnt[n][m]%MOD};
}
};
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla