这是一道经典的二维动态规划题目,题目如下:
这道题目用穷举的方法肯定是没有办法求解的,使用动态规划算法是最优秀的,我们可以想到每走到一格的路径数等于这个格子上面一格和左边一格的路径数之和,那么我们就可以定义动态规划的递推方程了:
dp[i][j]=dp[i−1][j]+dp[i][j−1]
然后初始状态,在同一列或者同一行的情况下,路径数只有一种,就是向下和向右。初始状态定义好了之后,有了递推方程,就可以写出代码:
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = 0
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
这就是经典的二维动态规划算法的解法,希望可以帮助大家更深层次地理解动态规划算法,理解初始状态和动态规划递推方程,就可以很好地解决类似的问题了,谢谢。