奔驰宝马游戏网站建设,安徽网站备案要多少时间,wordpress自定义文章目录,ai域名注册题目#xff1a;
放水果
把M个相同的水果放在N个同样的盘子里#xff0c;允许有的盘子空着不放#xff0c;问不同的放法数K是多少#xff1f;请注意#xff0c;5#xff0c;1#xff0c;1和1#xff0c;5#xff0c;1 是同一种放法。输入描述
第一行是测试数据的数目…题目
放水果
把M个相同的水果放在N个同样的盘子里允许有的盘子空着不放问不同的放法数K是多少请注意511和151 是同一种放法。输入描述
第一行是测试数据的数目t0 t 20随后的每行均包含二个整数M和N以空格分开。1MN10。输出描述
对输入的每组数据M和N在单独的行里输出相应的K。样例输入
5
2 5
3 3
9 5
2 10
5 1
样例输出
2
3
23
2
1面试官给了提示
dp[i][j]表示将i个水果放入j个盘子的放法数。我们首先初始化所有dp[i][0]为1因为将任何数量的水果放入0个盘子只有一种方法即不放。然后我们逐行填充动态规划表对于每个dp[i][j]如果j大于i则dp[i][j]等于dp[i][i]因为多余的盘子无法放入水果否则dp[i][j]等于dp[i][j-1]不使用第j个盘子的放法数加上dp[i-j][j]使用第j个盘子的放法数。最后dp[n][m]就是我们要求的结果。需要考虑两种情况一种是不使用第j个盘子另一种是使用第j个盘子。dp[i][j-1]表示的是第一种情况的放法数dp[i-j][j]表示的是第二种情况的放法数。将这两种情况的放法数相加就得到了总的放法数。当时是没看懂的主要也不太懂为啥dp[i-j][j]表示的是第二种情况的放法数 按照提示写了代码但是运行结果也不对
package mainimport fmt
import io// To execute Go code, please declare a func main() in a package main// The TestCase is shown below
// Input : 1 2
// Output : 3func main() {var t int_,err : fmt.Scanf(%d, t)if err ! nil {fmt.Println(err)return}for i : 0; i t; i {var M ,N int_,err : fmt.Scanf(%d %d, M, N)if err io.EOF {break}else{// fmt.Println(M, N)fmt.Println(test(M, N))// fmt.Println(Your result is : , a b)}}
}func test(M, N int) int {dp : make([][]int, M1)for i : 0; i M; i {dp[i] make([]int, N1)dp[i][0] 1}for i : 0; i M; i {for j : 1; j N; j {if j i {dp[i][j] dp[i][i]} else {dp[i][j] dp[i-j][j] dp[i][j-1]}}}return dp[M][N]
}有大佬路过可以给点帮助
