Python 算法之动态规划(Dynamic Programming)解析:二维矩阵中的醉汉(魔改版 leetcode 出界的路径数)

刘悦 at 
现在很多互联网企业学聪明了,知道应聘者有目的性的刷 Leetcode 原题,用来应付算法题面试,所以开始对这些题进行“魔改”,比如北京某电商平台的这道题:有一个正方形的岛,使用二维方形矩阵表示,岛上有一个醉汉,每一步可以往上下左右四个方向之一移动一格,如果超出矩阵范围他就死了,假设每一步的方向都是随机的(因为他是醉的),请计算 n 步以后他还活着的概率。例如:输入矩阵大小 2*2,起点(0,0),随机走出一步 n=1 输出 0.5 也就是有一半的几率还活着例如:输入矩阵大小 3*3,起点(1,1),随机走出一步 n=1 输出 1 也就是百分之百还活着乍一看有点懵,但是提取关键字:二维矩阵、上下……