首页 > 代码库 > [LeetCode]Unique Paths
[LeetCode]Unique Paths
题目:
从左上角到右下角的所有可能路径。
思路1:
回溯法去递归遍历所有的路径,但是复杂度太大,无法通过。checkPath方法实现
动态规划法,从左上角到每一格的路径数与它的上面一格和左边一格的路径和;
N(m,n)=N(m-1,n)+N(m,n-1);
注意:第一行和第一列的特殊情况。
package com.example.medium; /** * A robot is located at the top-left corner of a m x n grid (marked ‘Start‘ in the diagram below). * The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish‘ in the diagram below). * How many possible unique paths are there? * Above is a 3 x 7 grid. How many possible unique paths are there? * Note: m and n will be at most 100. * @author FuPing * */ public class UniquePaths { /** * 回溯法 * @param m 行边界 * @param n 列边界 * @param i 当前位置的行坐标 * @param j 当前位置的列坐标 * @return 可能的道路数量 * 时间超过了,20*15的规模就需要7870ms的时间 */ private int checkPath(int m,int n,int i,int j){ if(i == m && j == n)return 1;//到达最后一格 int roads = 0; if(i < m) roads += checkPath(m,n,i+1,j);//向左 if(j < n) roads += checkPath(m,n,i,j+1);//向下 return roads; } /** * 动态规划 N(m,n)=N(m-1,n)+N(m,n-1) * @param m * @param n * @return */ private int uniquePaths(int m, int n) { //return checkPath(m,n,1,1); int roadNums[][] = new int[m][n]; roadNums[0][0] = 1; int i = 0,j = 0; for(i = 1;i < m;i++)roadNums[i][0] = roadNums[0][0];//第一行 for(j = 1;j < n;j++)roadNums[0][j] = roadNums[0][0];//第一列 i = 1; j = 1; while(i < m && j < n){ roadNums[i][j] = roadNums[i][j - 1] + roadNums[i - 1][j]; j++; if(j == n){ i++; if(i == m)break; j = 1; } } return roadNums[m - 1][n - 1]; } public static void main(String[] args) { // TODO Auto-generated method stub long startTime = System.currentTimeMillis(); System.out.println(new UniquePaths().uniquePaths(20, 50)); long endTime = System.currentTimeMillis(); System.out.println("程序运行时间:"+(endTime-startTime) + "ms"); } }
[LeetCode]Unique Paths
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。