BoBo老师，一道饿了么的机试题

来源：8-4 组合问题 Combinations

weixin_慕标9554468

2020-08-18

给定一个n和一个m，使用1—n范围内的整数组成m个数，每个数字最多可以被使用4次，求有多少种组合方式。
请问LeetCode上有类似的题目吗？

更新：抱歉，是我没有表达清楚。从1-n中选择m个数形成组合（顺序无关），问有多少种组合方式，其中每个数字最多可以被使用4次。
示例：n = 2， m = 5；
结果：4中，因为：{1,1,1,1,2}，{1,1,1,2,2}，{1,1,2,2,2}，{1,2,2,2,2}

写回答

1回答

liuyubobobo

2020-08-19

没看懂题，什么叫“组成m个数”？给几个 sample？另外，数据范围是什么？

liuyubobobo

weixin_慕标9554468

猛的想是 dp。dp[i][j][k] 表示当前最多还有k 个 i 可以用，还差 j 个数字的组合数。dp[i][j][k] = dp[i][j - 1][k - 1]（if k > 0） + dp[i + 1][j][4]。dp[i][j - 1][k - 1] 的意思是当前选一个 i，然后还剩下 k - 1 个 i 可以选，还要 j - 1 个数组；dp[i + 1][j][4] 的意思是当前不选 i，那么下次从 i + 1 开始选，i + 1 能使用 4 次，还需要 j 个数字。求的是 dp[1][m][4]。

2020-08-19

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

查看课程

相似问题

bobo老师您好，关于leetcode-92号问题不需要考虑空指针异常的情况吗？

回答 1

没有理解这道题，麻烦bobo老师赐教~

回答 1

老师,问一道题

回答 1

bobo老师，对于动态规划和贪心算法的区别我不是很清楚呀？也不知道什么适合使用贪心算法？bobo老师有时间可以解答一下吗？

回答 1

bobo老师，二群里怎么没有您啊？

回答 1

打开慕课网App查看更多内容