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

#动态规划# 此题是一个典型的动态规划题，做动态规划一般都有五个步骤，先将题目改造为(n + 1)(m + 1)的点阵 1.确定dp数组下标及其数值的含义。本题为坐标为（i，j）的节点有dp[i][j]种走法 2.确定递推公式。本题为dp[i][j] = dp[i-1][j] + dp[i][j-1]. 3.初始化dp数组。易得（0，0）为0，上边界和左边界的点走法都为1 4.确定遍历顺序。两个for循环即可。 5.举例推导 import java.util.; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); //坐标为（i，j）的节点有dp[i][j]种走法 int[][] dp = new int[n + 1][m + 1]; //dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[0][0] = 0; for(int i = 1; i <= n;i++){ dp[i][0] = 1;//因为只能向下或向右,故点阵的上边界的点的走法为1 } for(int j = 1; j <= m; j++){ dp[0][j] = 1;//因为只能向下或向右，,故点阵的左边界的点的走法为1 } for(int i = 1; i <= n ;i++){ for(int j = 1; j <= m;j++){ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } System.out.println(dp[n][m]);//右下角的点对应的数值即为所有方案 } }