首页 > 其他分享 >335-获得分数的方法数

335-获得分数的方法数

时间:2023-03-05 17:22:45浏览次数:47  
标签:分数 题目 target 示例 335 解决 类型 方法 types

获得分数的方法数

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ,其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道,每道题目对应 marksi 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大,结果需要对 109 +7 取余。

注意,同类型题目无法区分。

比如说,如果有 3 道同类型题目,那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

示例 1:

输入:target = 6, types = [[6,1],[3,2],[2,3]]
输出:7
解释:要获得 6 分,你可以选择以下七种方法之一:

  • 解决 6 道第 0 种类型的题目:1 + 1 + 1 + 1 + 1 + 1 = 6
  • 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目:1 + 1 + 1 + 1 + 2 = 6
  • 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目:1 + 1 + 2 + 2 = 6
  • 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目:1 + 1 + 1 + 3 = 6
  • 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目:1 + 2 + 3 = 6
  • 解决 3 道第 1 种类型的题目:2 + 2 + 2 = 6
  • 解决 2 道第 2 种类型的题目:3 + 3 = 6
    示例 2:

输入:target = 5, types = [[50,1],[50,2],[50,5]]
输出:4
解释:要获得 5 分,你可以选择以下四种方法之一:

  • 解决 5 道第 0 种类型的题目:1 + 1 + 1 + 1 + 1 = 5
  • 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目:1 + 1 + 1 + 2 = 5
  • 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目:1 + 2 + 2 = 5
  • 解决 1 道第 2 种类型的题目:5
    示例 3:

输入:target = 18, types = [[6,1],[3,2],[2,3]]
输出:1
解释:只有回答所有题目才能获得 18 分。

提示:

1 <= target <= 1000
n == types.length
1 <= n <= 50
types[i].length == 2
1 <= counti, marksi <= 50

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/number-of-ways-to-earn-points
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

多重背包的模板题,想到了dp但是老是想不明白,先学一下以后补上。

code

标签:分数,题目,target,示例,335,解决,类型,方法,types
From: https://www.cnblogs.com/huangxk23/p/17180978.html

相关文章