题解 | #走方格的方案数#动态规划

严格来说，这道题的测试case是有问题的， 2*2 的数组结果应该是2，3*3的数组结果才是6。 题目的n*m的二维数组，当输入是2*2时，题目当成了3*3的二维数组了。

最终解法如下：读取 n 和 m 的值后，进行加+1，作为参数传入动态规划的算法。

当然，另一种方法是，在动态规划的算法里进行加一处理，以满足测试case的要求。

import java.util.Scanner;

/**
* @Author AlanKeene
* @Date 2022/05/04
* @Points Dynamic Programming
*/
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            // 读取的值各加1，以保证测试case能通过（题目的测试case定义有bug）
            int sum = dynamicProgramming(n + 1, m + 1);
            System.out.println(sum);
        }
    }

    // 动态规划
    public static int dynamicProgramming(int n, int m) {
        int[][] f = new int[n][m];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // 第一列或第一列只有一种走法 (因为只能向右或向下走)
                if (i == 0 || j == 0) {
                    f[i][j] = 1;
                } else {
                    // 其他格子的走法为： f[i][j] = f[i-1][j] + f[i][j-1]
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }

        // 结果为最后一项的值
        return f[n - 1 ][m - 1];
    }
  
}