【算法】【数组】【LintCode114】-不同的路径
学而不思则罔，思而不学则殆
【算法】【数组】【LintCode114】-不同的路径
题目
描述
有一个机器人的位于一个 m × n 个网格左上角。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
问有多少条不同的路径？
n和m均不超过100
且答案保证在32位整数可表示范围内。
Example 1:
Input: n = 1, m = 3
Output: 1
Explanation: Only one path to target position.
Example 2:
Input: n = 3, m = 3
Output: 6
Explanation:
D : Down
R : Right
1) DDRR
2) DRDR
3) DRRD
4) RRDD
5) RDRD
6) RDDR
算法一 - 递归
思路：节点只能右移或者下移，把所有的情况都走一遍。h = m+n
时间复杂度：
O
(
2
h
)
O(2^h)
O(2h)
空间复杂度：
O
(
2
h
)
O(2^h)
O(2h)
//算法一 - 递归 通过数组保存条数
public static int uniquePaths1(int m, int n) {
// write your code here
int[] flag = new int[1];
uniquePaths1(1, 1, m, n, flag);
return flag[0];
}
static void uniquePaths1(int currentM, int currentN, int m, int n, int[] flag) {
if (currentM == m && currentN == n) {
flag[0]++;
return;
} else if (currentM < m && currentN == n) {
//只等m相加
uniquePaths1(currentM + 1, currentN, m, n, flag);
} else if (currentM == m && currentN < n) {
//只等n相加
uniquePaths1(currentM, currentN + 1, m, n, flag);
} else {
uniquePaths1(currentM, currentN + 1, m, n, flag);
uniquePaths1(currentM + 1, currentN, m, n, flag);
}
}
算法二 - 动态规划
思路：到达【i,j】有两种方式，【i-1,j】右移或者【i,j-1】下移：DP[i][j] = DP[i-1][j]+DP[i][j-1]
D
P
[
i
]
[
j
]
=
{
1
i=0
1
j=0
D
P
[
i
]
[
j
]
=
D
P
[
i
−
1
]
[
j
]
+
D
P
[
i
]
[
j
−
1
]
i>0,j>0
DP[i][j]= \begin{cases} 1 & \text{i=0}\\ 1 & \text{j=0}\\ DP[i][j] = DP[i-1][j]+DP[i][j-1] & \text{i>0,j>0}\\ \end{cases}
DP[i][j]=⎩⎪⎨⎪⎧11DP[i][j]=DP[i−1][j]+DP[i][j−1]i=0j=0i>0,j>0
时间复杂度：
O
(
m
∗
n
)
O(m*n)
O(m∗n)
空间复杂度：
O
(
m
∗
n
)
O(m*n)
O(m∗n)
//动态规划
//DP[i][j] = DP[i-1][j]+DP[i][j-1]
public static int uniquePaths2(int m, int n) {
// write your code here
if (m == 1 || n == 1) {
return 1;
}
int[][] flag = new int[m][n];
for (int mIndex = 0; mIndex < m; mIndex++) {
for (int nIndex = 0; nIndex < n; nIndex++) {
if (mIndex == 0) {
flag[0][nIndex] = 1;
} else if (nIndex == 0) {
flag[mIndex][0] = 1;
} else {
flag[mIndex][nIndex] = flag[mIndex - 1][nIndex] + flag[mIndex][nIndex - 1];
}
}
}
return flag[m - 1][n - 1];
}