递归学习

灰太狼 2023-07-07 12:57 55阅读 0赞

## 递归+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)

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));
        }
    }

## 例二：机器人走方格 ##

有一个x\*y的方格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角，算出有几种走法  
f(x)=f(x-1,y)+f(x,y-1)

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));
        }
    }