题解 | #放苹果#

/*
本题虽然标记是简单, 但是我个人认为还是挺难的, 主要是状态不好确定, 状态内的各个子问题和原问题好像没说明区别
然后是状态确定好了, 但是方程不好确定. 用递归暴力破解比较好理解dp[i][j] = dp[i-j][j] + dp[i][j-1]
左边无限递归遍历左子树就是保证每个盘子都有一个分到极限, 右边右子树无限递归循环就是只有一个盘子装苹果
综合下来就是一个盘子到j个盘子装苹果的方法之和, 然后就是注意边界  i<0,j<=0 reture 0;//非法数据返回0 		  i==1 || j==1 || i==0  reture 1;
1个苹果  一个盘子  0个苹果,盘子为空
将以上思路放到动态规划的理解就是
i<j  dp[i][j] = dp[i][i] 
i>=j  dpij = dp[i-j][j]   +   dp[i][j-1]
			每个盘子都有苹果	至少一个盘子没有苹果
边界条件
dp[0][j] = 1;  dp[1][j] = 1;
dp[i][1] = 1;
*/
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        //设置动态规划数组dp[i][j]代表i个苹果放入j个盘子的放法
        int [][]dp = new int[m+1][n+1];
        //dp数组边界初始化
        //苹果为0时, 只有一种
        //苹果为1时, 只有一种
        //盘子为1时只有一种
        for (int i = 0; i <= n; i++)
        {
            dp[0][i] = 1;
            dp[1][i] = 1;
        }
        for (int i = 0; i <= m; i++)
        {
            dp[i][1] = 1;
        }

        //通过dp方程, 推导dp数组
        //i<=j, dp[i][j] = dp[i][i]
        //i>j , dp[i][j] = dp[i-j][j] + dp[i][j-1]
        for (int i = 2; i <=m ; i++)
        {
            for (int j = 2; j <=n ; j++)
            {
                if(i<j)//易错:不能等于
                {
                    dp[i][j] = dp[i][i];
                }
                else
                {
                    dp[i][j] = dp[i-j][j] + dp[i][j-1];
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}