312. Burst Balloons

https://leetcode.com/problems/burst-balloons/description/
DP
For each len = ir - il +1,
scan the array with k = il, ... , ir, where k is the last to burst
coin_k = nums[il-1] {nums[il] ... nums[k-1]} nums[k] {nums[k+1] ... nums[ir]} nums[ir+1],
dp[il][ir] = max of coin_k:

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        vector<vector<int>> dp(nums.size(), vector<int> (nums.size(), 0));
        for(int len=1; len<=n; len++) {
            for(int il=1; il <= n-len+1; il++) {
                int ir = il+len-1;
                for(int k=il; k<=ir; k++)
                    dp[il][ir] = max(dp[il][ir], nums[il-1]*nums[k]*nums[ir+1] + dp[il][k-1] + dp[k+1][ir]);
            }
        }
        return dp[1][n];
    }

416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/description/
DP1.
    bool canPartition(vector<int>& nums) {
        int sm = accumulate(nums.begin(), nums.end(), 0);
        if(sm&1) return false;
        bitset<10001> bs(1);
        for(int n: nums)
            bs |= (bs<<n);
        return bs[sm/2];
    }
DP2.
    bool canPartition(vector<int>& nums) {
        int sm = accumulate(nums.begin(), nums.end(), 0);
        if(sm & 1) return false;
        vector<bool> dp(sm+1, false);
        dp[0] = true;
        for(auto n: nums) {
            for(int i=dp.size()-1; i>=0; i--) {
                if(dp[i]) dp[i+n] = true;
            }
        }
        return dp[sm/2];
    }

494. Target Sum

https://leetcode.com/problems/target-sum/description/
Solution 1. DP
    int findTargetSumWays(vector<int>& nums, int S) {
        int sm =accumulate(nums.begin(), nums.end(), 0);
        if(sm < S) return 0;
        int target = sm + S;
        if(target & 1) return 0;
        target >>= 1;
        vector<int> dp(sm+1, 0);
        dp[0] = 1;
        for(auto n:nums) {
            for(int i=sm; i>=0; i--) {
                if(dp[i]) {
                    dp[i+n] += dp[i];
                }
            }
        }
        return dp[target];
    }

750. Number Of Corner Rectangles

    int countCornerRectangles(vector<vector<int>>& grid) {
        if(grid.size() <= 1) return 0;
        if(grid[0].size() <= 1) return 0;
        int NI = grid.size(), NJ = grid[0].size();
        int res=0;
        for(int i=0; i<NI; i++) {
            for(int ii=i+1; ii<NI; ii++) {
                int n=0;
                for(int j=0; j<NJ; j++) {
                    n += grid[i][j]*grid[ii][j];
                }
                res += n*(n-1)/2;
            }
        }
        return res;
    }

748. Shortest Completing Word

    string shortestCompletingWord(string lp, vector<string>& words) {
        transform(lp.begin(), lp.end(), lp.begin(), ::tolower);
        string res;
        int sz = 16;
        unordered_map<char,int> lm;
        for(char c: lp) {
            if(c>='a' && c<='z') lm[c]++;
        }
        for(auto &s: words) {
            if(s.size()<sz) {
                unordered_map<char,int> tm = lm;
                for(char c : s) if(tm.count(c)) tm[c]--;
                bool complete = true;
                for(auto &m: tm) {
                    if(m.second>0) {complete = false; break;}
                }
                if(complete) {
                    res = s;
                    sz = s.size();
                }
            }
        }
        return res;
    }

746. Min Cost Climbing Stairs

    int minCostClimbingStairs(vector<int>& cost) {
        int N = cost.size();
        if(N == 0) return 0;
        if(N == 1) return cost[0];
        if(N == 2) return min(cost[0], cost[1]);

        int c0 = cost[0], c1 = cost[1], c;
        for(int i=2; i<N; i++) {
            c = min(c0, c1) + cost[i];
            c0 = c1;
            c1 = c;
        }
        return min(c0, c1);
    }

638. Shopping Offers

https://leetcode.com/problems/shopping-offers/description/
bool operator<(vector<int>& s, vector<int>& n) {
    for(int i=0; i<n.size(); i++) {
        if(s[i]>n[i]) return false;
    }
    return true;
}
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int res = INT_MAX;
        shop(price, special, 0, needs, res, 0);
        return res;
    }
    void shop(vector<int>& price, vector<vector<int>>& special, int s, vector<int> needs, int&res, int sum){
        int I = price.size();
        if(s == special.size()) {
            for(int i=0; i<I; i++) sum += price[i] * needs[i];
            if(sum < res) res = sum;
            return;
        }
        shop(price, special, s+1, needs, res, sum);
        if(special[s]<needs)
        do {
            for(int i=0; i<I; i++) {
                needs[i] -= special[s][i];
            }
            sum += special[s][I];
            shop(price, special, s+1, needs, res, sum);
        } while(special[s]<needs);
       
    }
};

743. Network Delay Time

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int dmax = 1e7;
        vector<bool> used(N+1, false);
        vector<int> d(N+1, dmax);
        vector<vector<pair<int,int>>> u2v(N+1);
        for(int i=0; i<times.size(); i++) {
            u2v[times[i][0]].push_back({times[i][1], times[i][2]});
        }
        queue<int> q;
        q.push(K);
        d[K] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
// make current node available because signal delay may be smaller through a different path that has not been counted
            used[u] = false;
            for(auto &p: u2v[u]){
                int v = p.first, w = p.second;
                int dv = d[u] + w;
                if(dv < d[v]) {
                    d[v] = dv;
                    if(!used[v]) {
                        q.push(v);
                        used[v] = true;
                    }
                }
            }   
        }
        int res = 0;
        for(int i=1; i<N+1; i++) {
            if(d[i]>=dmax) return -1;
            res = max(res, d[i]);
        }
        return res;
    }

744. Find Smallest Letter Greater Than Target

    char nextGreatestLetter(vector<char>& letters, char target) {
        if(letters.back() <= target || letters.front()> target) return letters.front();
        int lo = 0, hi = letters.size() - 1, mi;
        while(lo<hi) {
            mi = (lo + hi) /2;
            if(mi == lo) break;
            if(target < letters[mi]) hi = mi;
            else if(target >= letters[mi]) lo = mi;
        }
        return letters[hi];
    }