题目:
园区某部门举办了Family Day,邀请员工及其家属参加;将公司园区视为一个矩形,起始园区设
置在左上角,终点园区设置在右下角;家属参观园区时,只能向右和向下园区前进,求从起始
园区到终点园区会有多少条不同的Q参观路径
输入描述
第一行为园区的长和宽:
后面每一行表示该园区是否可以参观,0表示可以参观,1表示不能参观
输出描述
输出为不同的路径数量
示例1:
输入:
3 3
0 0 0
0 1 0
0 0 0
输出:
2
题解:
相对来说比较明显的动态规划问题;
dp[i][j] 就表示到第i行j列位置的路径数量
那么初始值第一行dp[0][j] ,中间只要没有一个1,那么dp[0][j]=1,有一个1,那么这个位置,和后面位置dp[0][j]=0;
列也同理。
那么对于dp[i][j]。如果这个地方位置为1,那么dp[i][j]=0
如果不为1,那么dp[i][j] = dp[i-1][j]+dp[i][j-1];
最终输出dp[m-1][n-1]就是最终值了
代码:
import java.util.Scanner;
public class RouteCount {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] space = sc.nextLine().split(" ");
int m = Integer.valueOf(space[0]);
int n = Integer.valueOf(space[1]);
int a[][] = new int[m][n];
for(int i=0;i<m;i++){
String[] arr = sc.nextLine().split(" ");
for(int j=0;j<n;j++ ){
a[i][j] = Integer.valueOf(arr[j]);
}
}
int dp[][] = new int[m][n];
dp[0][0] = 1;
boolean hasOne = false;
for(int i=0;i<m;i++){
if(i==0&&a[0][0]==0){
hasOne = false;
}
if(hasOne){
dp[i][0] =0;
}
else if(a[i][0] ==1){
hasOne = true;
dp[i][0] =0;
}
else {
dp[i][0] = 1;
}
}
boolean strhasOne = false;
for(int j =0;j<n;j++){
if(j==0&&a[0][0]==0){
strhasOne = false;
}
if(strhasOne){
dp[0][j] =0;
}
else if(a[0][j] ==1){
strhasOne = true;
dp[0][j] =0;
}
else {
dp[0][j] = 1;
}
}
if(m<2||n<2){
System.out.println(dp[m-1][n-1]);
return;
}
for(int i = 1;i<m;i++){
for(int j=1;j<n;j++){
if(a[i][j]==0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
if(a[i][j]==1){
dp[i][j] = 0;
}
}
}
System.out.println(dp[m-1][n-1]);
}
}
验证: