将20个球放进12个不同的袋子,每个袋子可以放0-20个球,有多少种放法?分析如何计算,然后编程解答。
进阶问题:每个袋子只能放0个、2个或3个球,该如何计算?
public int ballBag(int bag, int ball) { int[][] dp = new int[bag + 1][ball + 1]; int i, j, k, sum; for (i = 1; i <= bag; i++) { dp[i][0] = 1; }//无论几个包,放入0个球的方法只有一种 for (j = 0; j <= ball; j++) { dp[1][j] = 1; }//无论几个球,放入1个包的方法也只有一种 for (i = 2; i <= bag; i++) { for (j = 1; j <= ball; j++) { sum = 0; for (k = 0; k <= j; k++) { sum += dp[i - 1][k]; } dp[i][j] = sum; } } return dp[bag][ball]; }