Leetcode 62. 不同路径

心路历程这道题基本就是Q-learning经典迷宫问题的简化版本所以肯定是用动态规划了毕竟RL中的时序差分估计法的本身也是来自于MC和动态规划的结合。如果正常正向思维思考的话首先看不到问题明显的循环结构考虑递归然后把当前所处位置i,j当作状态分析当前状态与下一个状态之间的联系。注意的点1、虽然简单但是要理解返回值中两个递归函数相加的含义2、无论横向纵向走到边界值都是只剩下一种走法了解法DP数组DPclassSolution:defuniquePaths(self,m:int,n:int)-int:dp[[1]*nfor_inrange(m)]foriinrange(m-2,-1,-1):forjinrange(n-2,-1,-1):dp[i][j]dp[i1][j]dp[i][j1]returndp[0][0]递归DPclassSolution:defuniquePaths(self,m:int,n:int)-int:# 动态规划cachedefdfs(i,j):ifim-1orjn-1:return1return1*dfs(i1,j)1*dfs(i,j1)returndfs(0,0)