Knapsack workout

knapsack-workout.md

Problem 1

Given an array with coins and target amount x. Find number of ways this sum can be formed if you can use each coin main times. lc

Hint

• Define function dp[len][x] - answer for subarray [0:len] for amount x.
• Find the recurent function.
• Simplify the recurent function dp[len][x] -> dp[x]

Solution

    int get(vector<int> const& dp, int i) {
        if (i >= 0)
            return dp[i];
        return 0;
    }
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (int i = 1; i <= coins.size(); ++i) {
            for (int j = 1; j <= amount; ++j)
                dp[j] = get(dp, j) + get(dp, j - coins[i - 1]);
            
        }
        return dp[amount];
    } 

Problem 2

Given array with integers, check if it can be partitioned into 2 subsequences such that the sum of elements in one is equal to the sum of elements in the other. lc

Solution

Difference with previous is that we cannot take the same element more than 1 time.

    bool canPartition(vector<int>& nums) {
        int s = accumulate(nums.begin(), nums.end(), 0);
        if (s % 2 == 1) return false;
        vector<bool> prev(s/2+1, false), cur(s/2+1, false);
        prev[0] = true;
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j <= s/2; ++j) {
                cur[j] = prev[j]; // this is the case when we skip current element
                if (j - nums[i-1] >= 0)
                    cur[j] = cur[j] || prev[j - nums[i-1]]; // this is the case when we take nums[i-1] element
            }
            swap(prev, cur);
        }
        return prev[s/2];
    }

Problem 3

LC 0-1 Knapsack. You are given strings containing only 0 and 1 and your task is to build a new strubg using them. But you can use only m 0s and n 1s.

Solution

without memory optimizations to keep it clean.

    pair<int,int> count(string const& s) {
        pair<int,int> res = {0, 0};
        for (char c : s)
            if (c == '0') ++res.first;
            else ++res.second;
        return res;
    }
    
    int findMaxForm(vector<string>& strs, int m, int n) {
        // dp[is][i0][i1] - how many strings we can take out out of first is strings
        // using only i0 0s and i1 1s
        vector< vector<vector<int>> > dp(strs.size()+1, vector<vector<int>>(m+1, vector<int>(n+1, 0)));
        for (int is = 1; is <= strs.size(); ++is) {
            auto[cnt0, cnt1] = count(strs[is-1]);
            for (int i0 = 0; i0 <= m; ++i0) {
                for (int i1 = 0; i1 <= n; ++i1) {
                    dp[is][i0][i1] = dp[is-1][i0][i1];
                    if (i0 - cnt0 >= 0 && i1 - cnt1 >= 0)
                        dp[is][i0][i1] = max(dp[is][i0][i1],
                                             dp[is-1][i0-cnt0][i1-cnt1] + 1);
                }
            }
        }
        return dp[strs.size()][m][n];
    }

Problem 4

For a number find the maximum of multiplication of it's addends, i.e. lc

Solution

The DP solution is below:

// Not the shortest and not optimal but works and easy to explain.
// dp[m][x] - maximum product with exactly m multipliers and the sum of elements is x

    int integerBreak(int n) {
        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
        iota(dp[1].begin(), dp[1].end(), 0);
        for (int m = 2; m <= n; ++m) { // number of elements
            dp[m][m] = 1;
            for (int x = m+1; x <= n; ++x) {// the target iself
                int maxBefore = numeric_limits<int>::min();
                for (int i = 1; i <= x - m; ++i)
                    maxBefore = max(maxBefore, dp[m-1][x - i]*i);
                dp[m][x] = maxBefore;    
            }
        }
        
        int res = numeric_limits<int>::min();
        for (int m = 2; m <= n; ++m)
            res = max(res, dp[m][n]);
        return res;
    }

There is an analythical solution as well. The key observation is that any multiplier in the optimal result cannot be greater than 3. To prove, assume that it is greater than 3: p > 3 => we can split it in two multipliers 3*(p-3) >= 3. Hence, optimal result P = 2^b * 3^b, n = 2 * a + 3 * b Another observation is that it is always preferable to take 3 instead of 2. So are trying to maximize number of 3 and there will be at maximum 2 2s.

    // analythical
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n%3 == 0) return pow(3, n/3);
        if (n%3 == 1) return pow(3, (n-4)/3) * 2 * 2;
        //if (n%3 == 2) 
        return pow(3, (n-2)/3)*2;
    }

Follow ups: https://leetcode.com/problems/k-inverse-pairs-array/

Problem 5

Count unique subsequencies in string. The idea is quite simple - for each character, if it is met first time answer dp[i+1] for S[:i] is just dp[i]*2 + 1 +1 for the subsequence made of this new character. If we saw this symbol, we need to subtract dp[ lastoccurence[s[i]] ].

Example:

dp={0,1,2}
aaa
  ^
dp[3] = 2*dp[2] - dp[1]
dp[1] describes count for S[:0] because dp[2] - takes into account all subsequences ending with s[1] and 
those which were before. We need to exclude only ending at s[1]

Solution

class Solution {
public:
    int distinctSubseqII(string S) {
        using lint = long long int;
        static const lint M = 1e9 + 7;
        
        // last occurence of particular letter
        vector<lint> lastOccurence(26, -1);
        vector<lint> dp(S.size() + 1, 0);
        for (int l = 1; l <= S.size(); ++l) {
            int ch = S[l-1] - 'a';
            if (lastOccurence[ch] == -1) // haven't seen this one
                dp[l] = ((2*dp[l-1])%M + 1)%M;   // assume we had {a, aa} and the new
                                         // letter is b, so we will have 
                                         // a,aa, ab,aab, b => 2*2+1
            else
                dp[l] = ((2*dp[l-1])%M + M - dp[lastOccurence[ch]])%M;
            // let s=aaa, dp = 0, 1, 2, ? Compute dp[3] = dp[2]*2 - dp[1] = 3
            // semantics is that we should not count twise subsequence a
            lastOccurence[ch] = l-1;
        }
        return dp.back();
    }
};