leetcode2585.获得分数的方法数

题目如下

数据范围

莫要被困难的外衣骗了，本题就是有数量限制的完全背包问题。显然我们可以令 f(x,y)为当有x种题目时分数为y时的方法数 令某种题目的数量为k 那么方法数应该是 f(x,y) = f(x - 1,y - k * (分值))其中(0 <= k <= 题目数量)

通过代码

class Solution { public: int waysToReachTarget(int target, vector<vector<int>>& types) { int mod = 1e9 + 7; int n = types.size(); vector<vector<int>> dp(2,vector<int>(target + 1)); int pre = 0,cur; dp[0][0] = 1; for(int i = 1;i <= types[0][0];i++){ if(i * types[0][1] <= target){ dp[0][i * types[0][1]] = 1; } } for(int i = 1;i < n;i++){ pre = (i - 1) % 2; cur = i % 2; for(int j = 0;j <= target;j++){ dp[cur][j] = 0; for(int k = 0;k <= types[i][0];k++){ if(k * types[i][1] <= j){ dp[cur][j] = (dp[cur][j] + dp[pre][j - k * types[i][1]]) % mod; } } } } return dp[cur][target] % mod; } };

利用滚动数组的思想优化后

class Solution { public: int waysToReachTarget(int target, vector<vector<int>>& types) { int mod = 1e9 + 7; int n = types.size(); vector<int> dp(target + 1); int pre = 0,cur; dp[0] = 1; for(int i = 1;i <= types[0][0];i++){ if(i * types[0][1] <= target){ dp[i * types[0][1]] = 1; } } for(int i = 1;i < n;i++){ for(int j = target;j >= 0;j--){ for(int k = 1;k <= types[i][0];k++){ if(k * types[i][1] <= j){ dp[j] = (dp[j] + dp[j - k * types[i][1]]) % mod; }else{ break; } } } } return dp[target] % mod; } };