动态规划解题

由于本题规定，只能向左和向下走，那么第一行和第一列都是由2开始，每次递增1。 alt

规律入上如图

因此我们可以得出，一个二维数组，然后得出如下等式 dp[n][m] = dp[n-1][m] + dp[n][m-1];


import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        int[][] dp = new int[n][m];
        dp[0][0] = 2;
        for (int i = 1; i <= m-1; i++) {
            dp[0][i] = dp[0][i-1] + 1;
        }
        for (int i = 1; i <= n-1; i++) {
            dp[i][0] = dp[i-1][0] + 1;
            for (int j = 1; j <= m-1; j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];//动态规划
            }
        }

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