题目及测试
package pid062;
/*不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
*/
public class main {
public static void main(String[] args) {
int[] testTable = {3,7,30,1};
int[] testTable2 = {2,3,30,2};
for (int i=0;i<testTable.length;i++) {
test(testTable[i],testTable2[i]);
}
}
private static void test(int ito,int ito2) {
Solution solution = new Solution();
int rtn;
long begin = System.currentTimeMillis();
System.out.println(ito+" "+ito2);
rtn = solution.uniquePaths(ito,ito2);//执行程序
long end = System.currentTimeMillis();
System.out.println(rtn);
System.out.println();
System.out.println("耗时：" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
解法1（成功，1ms，很快）
建立一个n行m列的数组，每个对应的数字是从左上角到到这一点能走的路线数，很明显，因为只能向右或向下，所以最上的一条边和最左的一条边只能从左上角一路走，都为1。
然后之后的所有的点的值为左边+上边。然后从第2行的第2个到最后一个开始计算，然后每行依次类推，右下角的最后一个计算，它的值就是结果
package pid062;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Solution {
//m列n行
public int uniquePaths(int m, int n) {
if(m<=0||n<=0){
return 0;
}
if(m==1||n==1){
return 1;
}
int[][] nums=new int[n][m];
for(int i=0;i<n;i++){
nums[i][0]=1;
}
for(int i=0;i<m;i++){
nums[0][i]=1;
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
nums[i][j]=nums[i-1][j]+nums[i][j-1];
}
}
return nums[n-1][m-1];
}
}
解法2（别人的方法）
不好的递归方法，耗时很长
来到某个结点，因为只能往右边和下面走，所以一个位置
[i,j]
依赖的位置是
[i-1,j]
和
[i,j-1]
位置两个点之前的数量之和； 所以我们把
[i,j]
看做是终点的话就得出下面的递归关系。
public int uniquePaths(int m, int n) {
return process(m,n,m,n);
}
public static int process(int m,int n,int i,int j){
if(i == 1 && j == 1){ //左上角
return 1;
}
if(i == 1){ //第一行
return process(m,n,i,j-1);
}
if(j == 1){ //第一列
return process(m,n,i-1,j);
}
return process(m,n,i-1,j) + process(m,n,i,j-1);
}
解法3（成功，0ms，极快）
比解法1更好
滚动优化
滚动数组的优化就是其实你在算
dp[i][j]
的时候，你左边的
dp[i][j-1]
还是
dp[j-1]
，而你上面的
dp[i-1][j]
还是
dp[j]
(没有更新)，所以可以只需要一个数组，所以滚动优化决定的是你更新的顺序；
//m列n行
public int uniquePaths(int m, int n) {
if(n==0||m==0){
return 0;
}
if(n==1||m==1){
return 1;
}
int[] row=new int[m];
for(int j=0;j<m;j++){
row[j]=1;
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
row[j]=row[j]+row[j-1];
}
}
return row[m-1];
}