要注意dp[0][0]要初始化为1。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 |
int
totalPath(vector<vector<bool> > &blocked) { int
m = blocked.size(); if
(m == 0) return
0; int
n = blocked[0].size(); if
(n == 0) return
0; vector<vector<int> > dp(m); for
(int
i = 0; i < m; i++) { dp[i].resize(n, 0); } if
(!blocked[0][0]) dp[0][0] = 1; for
(int
i = 0; i < m; i++) { for
(int
j = 0; j < n; j++) { if
(blocked[i][j]) { dp[i][j] == 0; } else
{ if
(i-1 >= 0) dp[i][j] += dp[i-1][j]; if
(j-1 >= 0) dp[i][j] += dp[i][j-1]; } } } return
dp[m-1][n-1];} |
原文：http://www.cnblogs.com/lautsie/p/3526019.html