class Solution {
public:
    int numSquares(int n) {
        if (n <= 0) return 0;
        vector<int> dp(n+1,INT_MAX); // n is the capacity/target 
        // dp[i] represent the number of perfect squre for sum i 
        dp[0]=0;

        for(int i=1 ; i<=n ; i++){          // Iterate over target sum
            for(int j=1 ; j*j <= i ; j++){   // Try all perfect squares <= i basially items that theif 
                dp[i] = min(dp[i],dp[i-j*j]+1); // include this one + previous count before this perfect squre
            }
        }
        return dp[n];
    }
};


/*
The Perfect Squares is Unbounded Knapsack problem because:
    You need to reach a target sum (n) using a given set of numbers (perfect squares like 1, 4, 9, 16,...).
    You can reuse numbers, meaning you can take a perfect square multiple times (just like unbounded knapsack).

Items	    -> Items with weights and values -> Perfect squares (1, 4, 9, ...)
Capacity	-> Knapsack weight limit W	-> Target sum n
Decision	-> Pick an item multiple times to maximize value -> Pick squares multiple times to minimize count
DP Formula	-> dp[i] = max(dp[i], dp[i - weight] + value) -> dp[i] = min(dp[i], dp[i - square] + 1)



*/

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1; // Base case

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
            }
        }
        return dp[n];
    }
};




/*

Items:   -> A set of items with weights and values.	-> Numbers from 1 to n, which can be used multiple times.
Capacity: -> The maximum weight the knapsack can hold -> 	Target sum (n) that needs to be split.
Decision: ->  Whether to pick an item multiple times to maximize value. -> 	Break n into numbers to maximize the product.
DP Formula: dp[i] = max(dp[i], dp[i - weight] + value). -> 	dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])).

*/

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        
        vector<unsigned long long int> dp(amount+1,0);
        dp[0]=1;                                // There's 1 way to make 0 (by taking no coins)
        for(auto coin:coins){                   // Iterate over each coin
            for(auto i=1;i<=amount;i++){        // Iterate over each amount
                if(coin<=i)                     // coin should be less than target anount 
                    dp[i]=dp[i]+dp[i-coin];     // Include the current coin + no of ways before this coin
            }
        }
        return dp[amount];                      // no of ways to reach amount
        

    }
};

// Pick a Coin and itertate through each amount

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        
        vector<unsigned long long int> dp(amount+1, INT_MAX);          
        // dp[i] represents the fewest number of coins to make up the amount i
        dp[0] = 0;  // There is 0 min ways to mke 0
        

        for (int i = 1; i <= amount; i++) {  // Itertate over all the amount 
            for (auto coin : coins) {        // Itertate over all the coins
                if (coin <= i) {             // if count is less than i otherwise we can't fit the coin
                    dp[i] = min(dp[i], dp[i-coin]+1);  
                    // last no of coins used at i vs (no of coins at i- coin + one more coin at i )
                }
            }
        }
        
        return dp[amount] == INT_MAX ? -1 : dp[amount]; // if not infi we can reach the sum 
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto a : nums) // Sum up the array
            sum += a;
        if (sum % 2 != 0) return false;  // Odd sum can't be partitioned equally
        int n = nums.size();
        int target = sum / 2; // target is equal half
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));

        // Base Case: Sum of 0 is always possible (empty subset)
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {  // Traverse through elements
            for (int j = 1; j <= target; j++) {  // Check all possible subset sums
                if (nums[i - 1] <= j) { // If current number can be included
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                } else { // If current number is too large
                    dp[i][j] = dp[i - 1][j];
                } 
            }
        }
        return dp[n][target]; // we can partinition the array of size n into target value 
    }
};

// If dp[i][j] is true, it means we can get sum j using the first i elements.
// dp[i][j]=dp[i−1][j](exclude item)       OR              dp[i−1][j−nums[i]](include item)

/*

0/1 Knapsack 
    Each element in nums represents an item with weight only (no value).
    The target sum of the subset is sum(nums) / 2, which acts as the knapsack capacity.
    For each number in nums, either include it in the subset or exclude it (just like choosing an item in 0/1 Knapsack).
    Each number can be used only once (bounded knapsack).

*/