# 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

```    public static int uniquePaths(int m, int n) {
int top = 1;
int left = 1;
return pathSum(top,left,m,n);
}
public static int pathSum(int top,int left,int m,int n){
if( left == m && top == n){
return 1;
}else if(top==n){
return pathSum(top,left+1,m,n);
}else if( left == m){
return pathSum(top+1,left,m,n);
}else if( left < m && top < n){
return pathSum(top+1,left,m,n)+ pathSum(top,left+1,m,n);
}
return 0;
}```

```1.简化版的递归
public int uniquePaths(int m, int n) {
return uniquePaths(1,1,m, n);
}

public int uniquePaths(int currentRow, int currentColumn, int m, int n){
if(currentRow==m || currentColumn==n){
return 1;
}
return uniquePaths(currentRow+1, currentColumn, m ,n ) + uniquePaths(currentRow,                    currentColumn+1, m, n);
}

2.利用杨辉三角求解:

public static int pathSum(int top,int left,int m,int n){
int[][] a = new int[m][n];

for (int i = 0; i < m; i++) {
a[i][0] = 1;
}

for (int i = 0; i < n; i++) {
a[0][i]=1;
}

for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
a[i][j] = a[i][j-1]+a[i-1][j];
}
}
return a[m-1][n-1];
}```

0 条评论

• ### 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find th...

• ### 219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two dist...

• ### 605. Can Place Flowers

Suppose you have a long flowerbed in which some of the plots are planted and som...

• ### BZOJ3498: PA2009 Cakes(三元环)

如果\(v\)的度数\(\leqslant M\)，那么就再暴力枚举\(v\)连出去的点\(t\)，看\(u\)与\(t\)是否联通(打标记)

• ### 洛谷P2831 愤怒的小鸟(状压dp)

直接状压dp一下，\(f[sta]\)表示干掉\(sta\)这个集合里面的鸟的最小操作数

• ### Java经典编程50题（面试笔试机试）

https://blog.csdn.net/alias_fa/article/details/52985112

• ### 挑战程序竞赛系列（8）：2.1一往直前！贪心法（其他）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### C语言——小学题目B卷解析（终）

第6题，简单说明：系统有默认的转化规则，就是从精度底的转化为精度高的，避免计算时精度的丢失。coding一下：

• ### 【BZOJ 1701】Cow School（斜率优化/动态凸包/分治优化）

小牛参加了n个测试，第i个测试满分是??pi,它的得分是??ti。老师去掉??/??ti/pi最小的d个测试，将剩下的总得分/总满分作为小牛的得分。小牛想知道多...

• ### HBU-DS2018SY-1-1 数组循环左移 （20 分）

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...