题解 | #放苹果#
放苹果
https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf
// mark一下 import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { // 状态转移方程 // 1. m < n 则: dp[i][j] = dp[i][i]; // 2. m >= n 则:dp[i][j] = dp[i][j - 1] + dp[i - j][j] // 终止条件 // m = 0 || m = 1,即: dp[0][j] = 1; dp[1][j] = 1; // n = 1,即: dp[i][1] = 1 public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { int m = in.nextInt(); int n = in.nextInt(); System.out.println(func(m, n)); } } public static int func(int m, int n) { int[][] dp = new int[m + 1][n + 1]; for (int k = 0; k <= n; k++) { dp[0][k] = 1; dp[1][k] = 1; } for (int k = 0; k <= m; k++) { dp[k][1] = 1; } // todo : 为啥i和j一定得从2开始,从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 - 1] + dp[i - j][j]; } } } return dp[m][n]; } }