Python算法之动态规划解析二维矩阵中的醉汉

　　现在很多互联网企业学聪明了，知道应聘者有目的性的刷Leetcode原题，用来应付算法题面试，所以开始对这些题进行魔改，比如北京某电商平台的这道题：
　　有一个正方形的岛，使用二维方形矩阵表示，岛上有一个醉汉，每一步可以往上下左右四个方向之一移动一格，如果超出矩阵范围他就死了，假设每一步的方向都是随机的（因为他是醉的），请计算n步以后他还活着的概率。例如：输入矩阵大小22，起点（0，0），随机走出一步n1输出0。5也就是有一半的几率还活着例如：输入矩阵大小33，起点（1，1），随机走出一步n1输出1也就是百分之百还活着
　　乍一看有点懵，但是提取关键字：二维矩阵、上下左右四个方向、矩阵范围、n步，有没有感到很熟悉？刷过Leetcode的同学一定已经联想到了Leetcode原题第576题：出界的路径数，难度等级为中等。
　　给定一个mn的网格和一个球。球的起始坐标为（i，j），你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动N次。找出可以将球移出边界的路径数量。答案可能非常大，返回结果mod1097的值。
　　和魔改版的题联系起来，所谓醉汉死了，其实就是移出边界，而每走一步都会有四种可能，所以所谓的存活率也就是当我们算出移出边界的路径数量之后，再除以方向的基数4，就可以算出存活率，相反也可以推算死亡率，归根结底，魔改版题的题眼还是算出移出边界的路径数，并不是最后问的存活率问题，这题只是用了一个并不是很讲究的障眼法，很有可能是该电商平台老板让手下的某个研发出道算法题招人用，而该研发已经被需求搞的晕头转向，无奈之下随便从leetcode复制了一道出来，随便改了改。
　　至于解法，下意识想到并且非常好理解的解法就是利用BFS（BreadthFirstSearch广度优先），因为醉汉最多只能移动N次，我们只要bfs依次遍历如果发现出界，就代表死亡，进行累加1，当bfs的深度大于N的时候break结束。理论上是没有任何问题。importcollectionsdefhowlikelyalive（m，n，N，i，j）：mod1097Qcollections。deque（〔（i，j，0）〕）res0whileQ：x，y，stepQ。popleft（）ifstepN：breakif0xmand0yn：Q。append（（x1，y，step1））Q。append（（x1，y，step1））Q。append（（x，y1，step1））Q。append（（x，y1，step1））else：res1numresmodifnum0：return1else：returnnum4print（howlikelyalive（2，2，1，0，0））
　　一般情况下，如果该岗位的技术要求并不高，使用bfs基本就算过关了，但是如果面试官想来一次压力面试（所谓压力面试就是想探探你的底），看看你的极限在哪里，就会要求你用效率更高的算法来解题。（这里需要简单分辨一下压力面试还是故意刁难，压力面试如果不会的话，礼貌询问就能拿到答案，而如果连面试官都不知道面试的答案，那肯定就是故意刁难了，也就没有面下去的必要了）。
　　我们再回到题目中想一想，魔改版题目并没有定义醉后随机走的步数N的范围，假设N的取值范围达到了50，我们对任意一个坐标点bfs有四个方向进行遍历，同时考虑往回走的可能性，那么复杂度达到了N的四倍，这个效率显然不会令人满意，所以当N相对小的情况下，比如只走1步，bfs是最优解，而范围过大就需要考虑dp了。
　　dp（DynamicProgramming）算法即是业界大名鼎鼎的动态规划算法了，其核心思路是把一个复杂的大问题拆成若干个子问题，通过解决子问题来逐步解决大问题，是不是和分治法有点像？关于分治算法可以参考这篇文章：当我们谈论算法我们在谈论什么：由疫情核酸检测想到的分治算法（DivideandConquer），但是和分治法有区别的地方是，使用动态规划思想有个前提：当且仅当每个子问题都是离散的（即每个子问题都不依赖于其他子问题时），才能使用动态规划。
　　再次回到题目，假设这个醉汉在第N步到达（mi，nj）位置有dp〔N〕〔mi〕〔nj〕种路径，可以假设一下当前状态如何从上一步移动中得来。其实就是上下左右四个方向移动过来的，而移动步数则是N1。defhowlikelyalive（m，n，N，i，j）：tmp〔〔〔0foriinrange（n）〕forjinrange（m）〕forkinrange（N1）〕forkinrange（1，N1）：forpinrange（m）：forqinrange（n）：if0p：up1else：uptmp〔k1〕〔p1〕〔q〕ifm1p：down1else：downtmp〔k1〕〔p1〕〔q〕if0q：left1else：lefttmp〔k1〕〔p〕〔q1〕ifn1q：right1else：righttmp〔k1〕〔p〕〔q1〕tmp〔k〕〔p〕〔q〕（updownleftright）1000000007numtmp〔N〕〔i〕〔j〕ifnum0：return1else：returnnum4returnnumprint（howlikelyalive（2，2，1，0，0））
　　结语：Leetcode算法题浩如烟海，想要每一道题都了如指掌，个人感觉难度不小，但是从这道二维矩阵中的醉汉来看，企业就算想要魔改，也是万变不离其宗，多多少少都有迹可循，所以我们在刷题的过程中，应该本着宁缺毋滥的原则，真实的掌握算法核心思想，才能够做到举一反三、百战不殆。