遞歸+dfs的學習
1. 自下而下解遞歸（遞推，數學歸納，動態規劃）
例1：上樓梯(遞歸/遞推）有個小孩正在上樓梯，樓梯有n階，小孩一次可以上1階，2階，3階。請實現一個方法，計算小孩有多少種上樓的方式，為了防止溢出，將結果mod 1000000007。反過來看，走到最後可能剩1,2,3步走完，這就可以利用之前求出的1,2,3的結果了。或者想象成f(n)=f(n-1)+f(n-2)+f(n-3)
<code>public class 上樓梯 { static long recursion(int n){//遞歸的解法，倒著寫，走到最後剩1,2,3其中的一個步數； if(n<0) return 0; if(n==0||n==1) return 1; if(n==2) return 2; return recursion(n-1)%mod+recursion(n-2)%mod+recursion(n-3)%mod; } static int mod=1000000007; static int recursion2(int n){//正向思維，迭代，效率更加優 if(n<0) return 0; if(n==0||n==1) return 1; if(n==2) return 2; if(n==3) return 4; int x1=1; int x2=2; int x3=4; for (int i = 4; i <=n; i++) { int x_1=x1; x1=x2%mod; x2=x3%mod; x3=((x1+x2)%mod+x_1)%mod; } return x3; } public static void main(String[] args) { System.out.println(recursion(4)); System.out.println(recursion2(4)); }}/<code>例二：機器人走方格
有一個x*y的方格，一個機器人只能走格點且只能向右或向下走，要從左上角走到右下角，算出有幾種走法f(x)=f(x-1,y)+f(x,y-1)
<code>public class Main { static int solve(int x,int y){ if(x==1||y==1) return 1; return solve(x-1,y)+solve(x,y-1); } static int solve1(int m,int n){ int[][] state=new int[m+1][n+1]; for(int i=1;i<=n;i++){ state[1][i]=1; } for(int i=1;i<=m;i++){ state[i][1]=1; } for (int i = 2; i <=m; i++) { for (int j = 2; j <= n; j++) { state[i][j]=state[i-1][j]+state[i][j-1]; } } return state[m][n]; } public static void main(String[] args) { System.out.println(solve(3,3)); System.out.println(solve1(3,3)); }}/<code>
分享到:
閱讀更多 小白學習日記yang 的文章
