2022-03-30:有m个同样的苹果,认为苹果之间无差别,
有n个同样的盘子,认为盘子之间也无差别,
还有,比如5个苹果如果放进3个盘子,
那么1、3、1和1、1、3和3、1、1的放置方法,也认为是一种方法。
如上的设定下,返回有多少种放置方法。
答案2022-03-30:
数的分裂。
自然智慧,递归。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
ret := ways3(5, 4)
fmt.Println(ret)
}
var dp [][]int
func ways3(apples, plates int) int {
if dp == nil {
dp = make([][]int, 11)
for i := 0; i < 11; i++ {
dp[i] = make([]int, 11)
}
for i := 0; i <= 10; i++ {
for j := 0; j <= 10; j++ {
dp[i][j] = -1
}
}
}
return process3(apples, plates, dp)
}
func process3(apples, plates int, dp [][]int) int {
if dp[apples][plates] != -1 {
return dp[apples][plates]
}
ans := 0
if apples == 0 {
ans = 1
} else if plates == 0 {
ans = 0
} else if plates > apples {
ans = process3(apples, apples, dp)
} else {
ans = process3(apples, plates-1, dp) + process3(apples-plates, plates, dp)
}
dp[apples][plates] = ans
return ans
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2021_12_4_week/Code05_SplitApples.java)