题解 | #放苹果#

// dp[i][j]表示将i+1个苹果放在j+1个盘子中的不同分法

// 一共分为三种情况，i，j

// 第一种，当苹果数i小于盘子数j，一定有一个盘子没放苹果，所以等价于(i, j-1);

// 第二种，当苹果数i等于盘子数j，将盘子放满只有一种情况，即每个都为1，然后加上盘子不放满的情况，所以等价于(i, j-1)+1;

// 第三种，当苹果数i大于盘子数j，盘子放满的话，相当于每个盘子中的苹果数都减一(手动写一下就容易发现)，即(i-j, j);

// 然后加上盘子不放满的情况，所以等价于(i, j-1)+(i-j, j);

// 则遍历顺序从上到下，左到右**

import java.util.*;

public class Main{

public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    while(scanner.hasNext()){
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(count(m, n));
    }
    scanner.close();
}

public static int count(int m, int n){
    int[][] dp = new int[m][n];
    

// 初始化

    for(int i = 0; i < m; i++) dp[i][0] = 1;
    for(int i = 0; i < n; i++) dp[0][i] = 1;

    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            if(i > j){
                dp[i][j] = dp[i-j-1][j] + dp[i][j-1];//mark，由于dp含义，手动写一下
            }else if(i == j){
                dp[i][j] = dp[i][j-1] + 1;
            }else{
                dp[i][j] = dp[i][j-1];
            }
        }
    }
    

//打印dp数组

     for(int i = 0; i < m; i++){
         for(int j = 0; j < n; j++){
            System.out.print(dp[i][j] + " ");
         }
         System.out.println();
     }
    
    return dp[m-1][n-1];
}

}