题解 | #走方格的方案数#

一开始思路错了，总想着找规律一步到位，但是利用算法会更简单：

1）动态规划
2）递归

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();

        //采用递归法或者动态规划
        //1.递归法
//         System.out.println(f(n,m));

        //2.动态规划
        int[][] dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==1||j==1) {
                    dp[i][j]=i+j;
                }else {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }

            }
        }
        System.out.println(dp[n][m]);
    }

    //递归法
    public static int f(int n,int m){
        if(n==1||m==1) return n+m;
        return f(n-1,m)+f(n,m-1);
    }
}