62. 不同路径
这一题用动态规划的方法去做,动态规划第一步就是要找到状态转移方程,本题中状态转移方程为:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
其中我们令 dp[i][j] 是到达 i, j 的可能路径数。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
ans = [ [1]*m for _ in range(n)]
for i in range(1,n):
for j in range(1,m):
ans[i][j] = ans[i-1][j] + ans[i][j-1]
return ans[n-1][m-1]