1538. Card Game II

0/1 knapsack problem

Version #2

93.96%
public boolean cardGame(int[] cost, int[] damage, int totalMoney, int totalDamage) {
        // Write your code here
        // max damage we can get with money j, with previous i cards
        int N = cost.length;
        int[] dp = new int[totalMoney + 1];
        // if we spend 0 money, then dp[x][0] = 0;
        for (int i = 1; i <= N; i++) {
            int[] curr = new int[totalMoney + 1];
            for (int j = 1; j <= totalMoney; j++) {
                // if we don't buy the (i-1)th item, we spend same money
                curr[j] = dp[j];
                if (j >= cost[i - 1]) {
                    curr[j] = Math.max(curr[j], damage[i - 1] + dp[j - cost[i - 1]]);
                }
                if (curr[j] >= totalDamage) {
                    return true;
                }
            }
            dp = curr;
        }
        return false;
    }




Version #1 Before space optimization
public class Solution {
    /**
     * @param cost: costs of all cards
     * @param damage: damage of all cards
     * @param totalMoney: total of money
     * @param totalDamage: the damage you need to inflict
     * @return: Determine if you can win the game
     */
    public boolean cardGame(int[] cost, int[] damage, int totalMoney, int totalDamage) {
        // Write your code here
        // max damage we can get with money j, with previous i cards
        int N = cost.length;
        int[][] dp = new int[N + 1][totalMoney + 1];
        // if we spend 0 money, then dp[x][0] = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= totalMoney; j++) {
                // if we don't buy the (i-1)th item, we spend same money
                dp[i][j] = dp[i - 1][j];
                if (j >= cost[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], damage[i - 1] + dp[i - 1][j - cost[i - 1]]);
                }
                if (dp[i][j] >= totalDamage) {
                    return true;
                }
            }
        }
        return false;
    }
}