动态规划：
- 为边界元素赋值
- 为非边界元素遍历赋值，只要确保遍历的时候左和上已经赋值完毕
class Solution {
public:
int uniquePaths(int m, int n) {
int a[m][n];
if (n<=0||m<=0){
return 0;
}
for(int i=0;i
其中数组可以动态开辟内存
int **a=new int* [m];
for(int i=0;i
python
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
list_mn = [[0 for i in range(n)] for j in range(m)]
if (m <= 0 or n <= 0):
return 0
for i in range(m):
list_mn[i][0] = 1
for i in range(n):
list_mn[0][i] = 1
for i in range(1,m):
for j in range(1,n):
list_mn[i][j] = list_mn[i - 1][j] + list_mn[i][j - 1]
return list_mn[m - 1][n - 1]
其中list_mn = [[0 for i in range(n)] for j in range(m)]是学到的新知识，python的二维数组初始化
官方python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
print(f)
for i in range(1, m):
for j in range(1, n):
f[i][j] = f[i - 1][j] + f[i][j - 1]
return f[m - 1][n - 1]
list_mn = [[1] * n] + [[1] + [0] * (n - 1) for i in range(m - 1)]这一句可以直接初始化
组合数学
n+m-2步中选n-1步向右，或m-1步向下
C
n
+
m
−
2
m
−
1
=
(
m
−
1
n
+
m
−
2
)
=
(
n
+
m
−
2
)
!
(
m
−
1
)
!
(
n
−
1
)
!
=
(
n
+
m
−
2
)
(
n
+
m
−
1
)
⋯
n
(
m
−
1
)
!
C_{n+m-2}^{m-1}=tbinom{m-1}{n+m-2}=frac{(n+m-2)!}{(m-1)!(n-1)!}=frac{(n+m-2)(n+m-1)cdots n}{(m-1)!}
Cn+m−2m−1=(n+m−2m−1)=(m−1)!(n−1)!(n+m−2)!=(m−1)!(n+m−2)(n+m−1)⋯n
cpp
#include
using namespace std;
class Solution {
public:
int uniquePaths(int m, int n) {
long long ans=1;
for(int x=n,y=1;y
python
class Solution(object):
def uniquePaths(self, m, n):
x=n
y=1
ans=1
while(y
python 官解
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return comb(m + n - 2, n - 1)
学到了新知识点 : 是参数建议符 ->是返回建议符，comb是math块是组合数（需要3.8+的python）英文单词为combination
