Word Break Problem

Given a string s and a ditcionary wordDict, determine if s can be segmented into space-sepaarted words from the dictionary.

Backtracking with Memoization

bool canSegment(const string& s, const unordered_set<string>& dict, vector<int>& memo, int pos) {
    if(pos >= s.size()) return true;
    if(memo[pos] != -1) return memo[pos];
    
    for(int i = pos; i < s.size(); i++) {
        string segment = s.substr(pos, i-pos+1);
        if(dict.count(segment) && canSegment(s, dict, memo, i+1)) {
            return memo[pos] = true;
        }
    }
    return memo[pos] = false;
}

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<int> memo(s.size(), -1);
    return canSegment(s, dict, memo, 0);
}

Dynamic Programming Approach

bool wordBreakDP(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size()+1, false);
    dp[0] = true;
    
    for(int i = 1; i <= s.size(); i++) {
        for(int j = 0; j < i; j++) {
            if(dp[j] && dict.count(s.substr(j, i-j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

House Robber Series

Basic House Robber

int robBasic(vector<int>& nums) {
    if(nums.empty()) return 0;
    if(nums.size() == 1) return nums[0];
    
    vector<int> dp(nums.size());
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    
    for(int i = 2; i < nums.size(); i++) {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    return dp.back();
}

Circular Arrangement

int robRange(vector<int>& nums, int start, int end) {
    if(start == end) return nums[start];
    
    vector<int> dp(nums.size());
    dp[start] = nums[start];
    dp[start+1] = max(nums[start], nums[start+1]);
    
    for(int i = start+2; i <= end; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    return dp[end];
}

int robCircular(vector<int>& nums) {
    if(nums.size() == 1) return nums[0];
    int case1 = robRange(nums, 0, nums.size()-2);
    int case2 = robRange(nums, 1, nums.size()-1);
    return max(case1, case2);
}

Binary Tree Structure

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

pair<int, int> robTree(TreeNode* root) {
    if(!root) return {0, 0};
    
    auto left = robTree(root->left);
    auto right = robTree(root->right);
    
    int robCurrent = root->val + left.first + right.first;
    int skipCurrent = max(left.first, left.second) + max(right.first, right.second);
    
    return {skipCurrent, robCurrent};
}

int robTreeSolution(TreeNode* root) {
    auto result = robTree(root);
    return max(result.first, result.second);
}

Stock Trading Problems

Single Transaction

int maxProfitSingle(vector<int>& prices) {
    if(prices.empty()) return 0;
    
    vector<vector<int>> dp(prices.size(), vector<int>(2));
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    
    for(int i = 1; i < prices.size(); i++) {
        dp[i][0] = max(dp[i-1][0], -prices[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
    }
    return dp.back()[1];
}

Multiple Transactions

int maxProfitMultiple(vector<int>& prices) {
    if(prices.empty()) return 0;
    
    vector<vector<int>> dp(2, vector<int>(2));
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    
    for(int i = 1; i < prices.size(); i++) {
        dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-1)%2][1] - prices[i]);
        dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-1)%2][0] + prices[i]);
    }
    return dp[(prices.size()-1)%2][1];
}