首页 > 代码库 > unique path 阶梯
unique path 阶梯
一、思路
迷宫出逃不知道还记得不?
只不过这里的迷宫有进口和出口了。
递归解题,但是数据过大就超时了
import java.util.Stack; public class UniquePath { public int[][] path={ {0,0,0,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,0,0,0} }; public int[][] dire={ {1,0}, {0,1} }; public int count=0; /** * 查找线路递归 */ public void findPath(int x,int y){ if(x==2&&y==6) count++; if(x>2||y>6) return; for(int i=0;i<2;i++){ x+=dire[i][0]; y+=dire[i][1]; } } /** * 非递归程序 * 查找路径 */ public int uniquePaths(int m, int n) { Stack s=new Stack(); int step[]=new int[]{0,0}; s.push(step); int count=0; while(!s.isEmpty()){ step=(int[]) s.pop(); for(int i=0;i<2;i++){ int x=step[0]+dire[i][0]; int y=step[1]+dire[i][1]; if(x==m-1&&y==n-1){//这里是一个终点 count++; }else if(x>=0&&x<=m-1&&y>=0&&y<=n-1){//还在找路 s.push(new int[]{x,y}); }else{//超出了数据 continue; } } } return count; } public static void main(String[] args) { UniquePath up=new UniquePath(); //up.findPath(0,0); //System.out.println(up.count); System.out.println(up.uniquePaths(23, 12)); } }
二、递归和非递归区别
递归数据量多大可能堆栈溢出,耗时在开销的部分。
非递归借助于队列。
递归为什么比非递归耗时?
开销大,因为维护的数据越来越多。么次维护一个新的函数。非递归维护的数据就少。
递归代码清晰,非递归复杂
三、依然超时
在23,12的时候还是超时???
要换个想法了
unique path 阶梯
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。