# 2585. Number of Ways to Earn Points
###### tags: `Leetcode` `Hard` `Dynamic Programming` `Knapsack Problem`
Link: https://leetcode.com/problems/number-of-ways-to-earn-points/description/
## 思路
背包问题
dp[i][j]表示用前```i```个物品凑到```j``` points有多少种方法
k表示当前物品我们要用几个 注意k是从0开始的 因为我们可以一个也不拿

## Code

class Solution {
public int waysToReachTarget(int target, int[][] types) {
int[][] dp = new int[types.length+1][target+1];
int mod = (int)(1e9+7);
dp[0][0] = 1;
for(int i=0; i<types.length; i++){
for(int j=0; j<=target; j++){
for(int k=0; k<=types[i][0]; k++){
if(j+k*types[i][1]<=target){
dp[i+1][j+k*types[i][1]] = (dp[i+1][j+k*types[i][1]]+dp[i][j])%mod;
}
}
}
}

return dp[types.length][target];
}
}

空间优化

class Solution {
public int waysToReachTarget(int target, int[][] types) {
int[] dp = new int[target+1];
int mod = (int)(1e9+7);
dp[0] = 1;
for(int i=0; i<types.length; i++){
int[] newDP = dp.clone();
for(int j=0; j<=target; j++){
for(int k=1; k<=types[i][0]; k++){
if(j+k*types[i][1]<=target){
newDP[j+k*types[i][1]] = (newDP[j+k*types[i][1]]+dp[j])%mod;
}
}
}
dp = newDP;
}

return dp[target];
}
}