百度站长资源平台,四川省建设厅官方网站首页,wordpress上传打文件失败,代码做网站常用单词转载自#xff1a;http://blog.csdn.net/linhuanmars/article/details/22126357
原题链接: http://oj.leetcode.com/problems/unique-paths/
这道题是比较典型的动态规划的题目。模型简单#xff0c;但是可以考核动态规划的思想。我们先说说brute force的解法#xff0c;…转载自http://blog.csdn.net/linhuanmars/article/details/22126357
原题链接: http://oj.leetcode.com/problems/unique-paths/
这道题是比较典型的动态规划的题目。模型简单但是可以考核动态规划的思想。我们先说说brute force的解法比较容易想到用递归到达某一格的路径数量等于它的上面和左边的路径数之和结束条件是走到行或者列的边缘。因为每条路径都会重新探索时间复杂度是结果数量的量级不是多项式的复杂度。代码如下 [java] view plaincopy public int uniquePaths(int m, int n) { return helper(1,1,m,n); } private int helper(int row, int col, int m, int n) { if(rowm coln) return 1; if(rowm || coln) return 0; return helper(row1,col,m,n)helper(row,col1,m,n); } 上面的代码放到LeetCode中跑会超时因为不是多项式量级的。其实上一步中递推式已经出来了就是res[i][j]res[i-1][j]res[i][j-1]这样我们就可以用一个数组来保存历史信息也就是在i行j列的路径数这样每次就不需要重复计算从而降低复杂度。用动态规划我们只需要对所有格子进行扫描一次到了最后一个得到的结果就是总的路径数所以时间复杂度是O(m*n)。而对于空间可以看出我们每次只需要用到上一行当前列以及前一列当前行的信息我们只需要用一个一维数组存上一行的信息即可然后扫过来依次更替掉上一行对应列的信息即可因为所需要用到的信息都还没被更替掉所以空间复杂度是O(n)其实如果要更加严谨我们可以去行和列中小的那个然后把小的放在内层循环这样空间复杂度就是O(min(m,n))下面的代码为了避免看起来过于繁杂就不做这一步了有兴趣的朋友可以实现一下比较简单不过代码有点啰嗦。实现的代码如下 [java] view plaincopy public int uniquePaths(int m, int n) { if(m0 || n0) return 0; int[] res new int[n]; res[0] 1; for(int i0;im;i) { for(int j1;jn;j) { res[j] res[j-1]; } } return res[n-1]; } 上面的方法用动态规划来求解如果我们仔细的看这个问题背后的数学模型其实就是机器人总共走mn-2步其中m-1步往下走n-1步往右走本质上就是一个组合问题也就是从mn-2个不同元素中每次取出m-1个元素的组合数。根据
组合
的计算公式我们可以写代码来求解即可。代码如下 [java] view plaincopy public int uniquePaths(int m, int n) { double dom 1; double dedom 1; int small mn? m-1:n-1; int big mn? n-1:m-1; for(int i1;ismall;i) { dedom * i; dom * smallbig1-i; } return (int)(dom/dedom); } 上面的代码求解了组合的结果只需要做一次行或者列的扫描所以时间复杂度是O(min(m,n))而空间复杂度是O(1)。比起上面的两种解法更优。不过这里有个弊端就是如果代码中的dom和dedom如果不是double而是用int那么会很容易越界因为这是一个阶乘所以大家在面试中讨论这种方法要注意和提及越界的问题。上面介绍了几种方法来求解这个问题其实都是比较简单的模型只是提供了不同的思路。
Unique Paths II
是这道题的扩展给机器人增加了障碍有兴趣的朋友可以联系一下。
