33 动态规划和递归求解不同路径II

问题描述：一个机器人位于一个m×n网格的左上角(起始点在下图中标记为Start)，机器人每次只能向下或者向右移动一步，机器人试图到达网格的右下角，机器人试图到达网格的右下角，现在考虑网格中有障碍物，那么从左上角到右下角有多少条路径。

递归求解：可以用一个引用数据类型Integer来存储

public void pathNum(int [][]matrix,int rowIndex,int columnIndex,?Integer intNumber)
{
if(rowIndex==matrix.length||columnIndex==matrix[0].length||matrix[rowIndex][columnIndex]==1)
return;
if(rowIndex==matrix.length-1&&columnIndex==matrix[0].length-1)
{
intNumber+=1;
return;
}
pathNum(matrix,rowIndex+1,columnIndex,intNumber);
pathNum(matrix,rowIndex,columnIndex+1,intNumber);
}
public int PathNum(int[][]matrix)
{
Integer intNumber=new Integer(0);
pathNum(matrix,0,0,intNumber);
???????return intNumber.parseInt();

}

递归求解的第二种解法：每次统计子分组的个数,并且使用map进行统计，进行优化

public int pathNum(int [][]matrix,int rowIndex,int columnIndex,Map<String,Integer> map)
{
if(rowIndex==matrix.length||columnIndex==matrix[0].length||matrix[rowIndex][columnIndex]==1)
return 0;
if(rowIndex==matrix.length-1&&columnIndex==matrix[0].length-1)
{
return 1;
}
if (map.containsKey(rowindex+"-"+columnIndex))
return map.get(rowindex+"-"+columnIndex);
else
{
int pathNumber=pathNum(matrix,rowIndex+1,columnIndex,map)+pathNum(matrix,rowIndex,columnIndex+1,map)
map.put(rowindex+"-"+columnIndex,pathNumber);
}
return map.get(rowindex+"-"+columnIndex);
}

public int PathNum(int [][]matrix)
{
Map<String,Integer> map=new HashMap<>();
pathNum(matrix,0,0,map);
return map.get((matrix.length-1)+"-"+(matrix[0].length-1));
}

动态规划方法求解：定义dp[i][j]为从开头到[i][j]位置的条数，如果matrix[i][j]==1,则dp[i][j]=0;

public int pathNum(int [][]nums)
{
int []dp=new int [nums.length][nums[0].length];
dp[0][0]=1;
for(int i=1;i<nums.length;i++)
{
for(int j=1;j<nums[i].length;j++)
{
if(nums[i][j]==0)
{
dp[i][j]==0;
}
else
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[nums.length-1][nums[0].length];
}