题目地址：
https://www.lintcode.com/problem/card-game/description
给定
n
n
n个物品，其价值为数组
A
A
A，成本为数组
B
B
B，问在给定总预算
c
c
c和最小总价值
p
p
p的情况下，有多少个组合可以使得总成本是小于
c
c
c，并且总价值是大于
p
p
p的。题目保证每个物品的价值和成本都是非负的（注意，这里可以是
0
0
0）。答案模
1
0
9
+
7
10^9+7
109+7后返回。
思路是动态规划。设
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k]是前
i
i
i个物品（从
0
0
0开始计数），总价值大于等于
j
j
j并且成本恰好等于
k
k
k的方案数。那么根据第
i
i
i个物品是否选，可以分为两种情况，如果不选，那么方案数就是
f
[
i
−
1
]
[
j
]
[
k
]
f[i-1][j][k]
f[i−1][j][k]；如果选，那么方案数就是
f
[
i
−
1
]
[
max
{
0
,
j
−
A
[
i
]
}
]
[
k
−
B
[
i
]
]
f[i-1][\max\{0,j-A[i]\}][k-B[i]]
f[i−1][max{0,j−A[i]}][k−B[i]]，所以就有：
f
[
i
]
[
j
]
[
k
]
=
f
[
i
−
1
]
[
j
]
[
k
]
+
f
[
i
−
1
]
[
max
{
0
,
j
−
A
[
i
]
}
]
[
k
−
B
[
i
]
]
f[i][j][k]=f[i-1][j][k]+f[i-1][\max\{0,j-A[i]\}][k-B[i]]
f[i][j][k]=f[i−1][j][k]+f[i−1][max{0,j−A[i]}][k−B[i]]边界条件，考虑第
0
0
0个物品是否选。如果不选，则
f
[
0
]
[
0
]
[
0
]
=
1
f[0][0][0]=1
f[0][0][0]=1，别的
f
[
0
]
[
.
>
0
]
[
0
]
=
0
f[0][.>0][0]=0
f[0][.>0][0]=0；如果选，则
f
[
0
]
[
.
≤
A
[
0
]
]
[
B
[
i
]
]
=
1
f[0][.\le A[0]][B[i]]=1
f[0][.≤A[0]][B[i]]=1，所以算
f
[
0
]
f[0]
f[0]的时候，要将两种情况加总。代码如下：
public class Solution {
/**
* @param n: The number of cards
* @param totalProfit: The totalProfit
* @param totalCost: The totalCost
* @param a: The profit of cards
* @param b: The cost of cards
* @return: Return the number of legal plan
*/
public int numOfPlan(int n, int totalProfit, int totalCost, int[] a, int[] b) {
// Write your code here
int MOD = (int) (1E9 + 7);
// dp[i][j][k]是从前i + 1个物品里选，价值大于等于j的且成本恰好等于k的组合总数
int[][][] dp = new int[n][totalProfit + 2][totalCost];
// 如果第0个物品不选
dp[0][0][0] = 1;
for (int i = 0; i <= Math.min(a[0], totalProfit + 1); i++) {
// 这里要注意b[0] = 0的情况，所以要写成 += 1
dp[0][i][b[0]] += 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= totalProfit + 1; j++) {
for (int k = 0; k < totalCost; k++) {
dp[i][j][k] = dp[i - 1][j][k];
if (k >= b[i]) {
dp[i][j][k] += dp[i - 1][Math.max(0, j - a[i])][k - b[i]];
}
dp[i][j][k] %= MOD;
}
}
}
int res = 0;
for (int i = 0; i < totalCost; i++) {
res += dp[n - 1][totalProfit + 1][i];
res %= MOD;
}
return res;
}
}
时空复杂度
O
(
n
p
c
)
O(npc)
O(npc)。
可以用滚动数组优化。代码如下：
public class Solution {
/**
* @param n: The number of cards
* @param totalProfit: The totalProfit
* @param totalCost: The totalCost
* @param a: The profit of cards
* @param b: The cost of cards
* @return: Return the number of legal plan
*/
public int numOfPlan(int n, int totalProfit, int totalCost, int[] a, int[] b) {
// Write your code here
int MOD = (int) (1E9 + 7);
// dp[i][j][k]是从前i + 1个物品里选，价值大于等于j的且成本恰好等于k的组合总数
int[][][] dp = new int[2][totalProfit + 2][totalCost];
dp[0][0][0] = 1;
for (int i = 0; i <= Math.min(a[0], totalProfit + 1); i++) {
dp[0][i][b[0]] += 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= totalProfit + 1; j++) {
for (int k = 0; k < totalCost; k++) {
dp[i & 1][j][k] = dp[i - 1 & 1][j][k];
if (k >= b[i]) {
dp[i & 1][j][k] += dp[i - 1 & 1][Math.max(0, j - a[i])][k - b[i]];
}
dp[i & 1][j][k] %= MOD;
}
}
}
int res = 0;
for (int i = 0; i < totalCost; i++) {
res += dp[n - 1 & 1][totalProfit + 1][i];
res %= MOD;
}
return res;
}
}
时间复杂度不变，空间
O
(
p
c
)
O(pc)
O(pc)。
本文地址：https://blog.csdn.net/qq_46105170/article/details/110121972
