[itint5]棋盘漫步 - 阿牧遥 - 博客园
要注意dp[0][0]要初始化为1。
https://github.com/ralphite/ITint5-Answers-Java/blob/master/%E6%A3%8B%E7%9B%98%E6%BC%AB%E6%AD%A5.java
public int totalPath(boolean[][] blocked) {
if(blocked==null || blocked.length==0 || blocked[0].length==0) {
return 0;
}
int m = blocked.length;
int n = blocked[0].length;
int[][] paths = new int[m][n];
if(!blocked[0][0]) {
paths[0][0]=1;
}else {
return 0;
}
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(i==0 && j==0) {
continue;
}else if(i==0) {
if(blocked[0][j]) {
paths[0][j] = 0;
} else {
paths[0][j] = paths[0][j-1];
}
}else if(j==0) {
if(blocked[i][0]) {
paths[i][0] = 0;
} else {
paths[i][0] = paths[i-1][0];
}
}else {
if(blocked[i][j]) {
paths[i][j] = 0;
} else {
paths[i][j] = paths[i-1][j] + paths[i][j-1];
}
}
}
}
return paths[m-1][n-1];
}
Read full article from [itint5]棋盘漫步 - 阿牧遥 - 博客园
要注意dp[0][0]要初始化为1。
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];
}
public int totalPath(boolean[][] blocked) {
if(blocked==null || blocked.length==0 || blocked[0].length==0) {
return 0;
}
int m = blocked.length;
int n = blocked[0].length;
int[][] paths = new int[m][n];
if(!blocked[0][0]) {
paths[0][0]=1;
}else {
return 0;
}
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(i==0 && j==0) {
continue;
}else if(i==0) {
if(blocked[0][j]) {
paths[0][j] = 0;
} else {
paths[0][j] = paths[0][j-1];
}
}else if(j==0) {
if(blocked[i][0]) {
paths[i][0] = 0;
} else {
paths[i][0] = paths[i-1][0];
}
}else {
if(blocked[i][j]) {
paths[i][j] = 0;
} else {
paths[i][j] = paths[i-1][j] + paths[i][j-1];
}
}
}
}
return paths[m-1][n-1];
}
Read full article from [itint5]棋盘漫步 - 阿牧遥 - 博客园