题目地址：

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