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

经典的动态规划题目：考虑右下角只能从上方或者左方经过，那么可以列出状态转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1].注意初始条件，第一行和第一列都只能有一种走法。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int a = in.nextInt();
            int b = in.nextInt();
            int dp[][] = new int[a+1][b+1];
            for(int i=0;i<dp[0].length;++i)
                dp[0][i] = 1;
            for(int i=0;i<dp.length;++i)
                 dp[i][0] = 1;
            for(int i=1;i<=a;++i){
                for(int j = 1;j<=b;++j){
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
            System.out.println(dp[a][b]);
        }
    }
}