Minimum Path Sum in a Grid

Finding the minimum path sum from the top-left to the bottom-right of a grid is a classic dynamic programming problem. To optimize space complexity, we can use a 1D array instead of a 2D matrix to store the DP states, updating the array iteratively as we traverse each row.

#include <vector>
#include <algorithm>

class GridSolver {
public:
    int findMinPathSum(std::vector<std::vector<int>>& matrix) {
        int rowCount = matrix.size();
        int colCount = matrix[0].size();
        std::vector<int> dp(colCount, 0);
        
        dp[0] = matrix[0][0];
        for (int c = 1; c < colCount; ++c) {
            dp[c] = dp[c - 1] + matrix[0][c];
        }
        
        for (int r = 1; r < rowCount; ++r) {
            dp[0] += matrix[r][0];
            for (int c = 1; c < colCount; ++c) {
                dp[c] = std::min(dp[c - 1], dp[c]) + matrix[r][c];
            }
        }
        return dp[colCount - 1];
    }
};

Edit Distance

The edit distance between two strings is the minimum number of insertions, deletions, and substitutions required to transform one string into the other. Because transforming string A to B requires the same operations as transforming B to A (just in reverse), we can build a 2D table where distTable[i][j] represents the minimum operations needed to convert the first i characters of the source string to the first j characters of the target string.

#include <vector>
#include <string>
#include <algorithm>

class StringTransform {
public:
    int calculateMinDistance(std::string src, std::string tgt) {
        int srcLen = src.length();
        int tgtLen = tgt.length();
        std::vector<std::vector<int>> distTable(srcLen + 1, std::vector<int>(tgtLen + 1, 0));
        
        for (int i = 0; i <= srcLen; ++i) distTable[i][0] = i;
        for (int j = 0; j <= tgtLen; ++j) distTable[0][j] = j;
        
        for (int i = 1; i <= srcLen; ++i) {
            for (int j = 1; j <= tgtLen; ++j) {
                if (src[i - 1] == tgt[j - 1]) {
                    distTable[i][j] = distTable[i - 1][j - 1];
                } else {
                    distTable[i][j] = 1 + std::min({distTable[i - 1][j - 1], 
                                                     distTable[i - 1][j], 
                                                     distTable[i][j - 1]});
                }
            }
        }
        return distTable[srcLen][tgtLen];
    }
};

Best Time to Buy and Sell Stock - Single Transaction

To maximize profit with only one transaction, we need to find the maximum difference between a subsequent price and a preceding price. This is achieved by continuous tracking the minimum price encountered so far and calculating the potential profit if sold on the current day.

#include <vector>
#include <algorithm>

class StockTrader1 {
public:
    int maxSingleProfit(std::vector<int>& priceHistory) {
        int lowestSeen = priceHistory[0];
        int maxGain = 0;
        for (size_t i = 1; i < priceHistory.size(); ++i) {
            if (priceHistory[i] < lowestSeen) {
                lowestSeen = priceHistory[i];
            } else {
                maxGain = std::max(maxGain, priceHistory[i] - lowestSeen);
            }
        }
        return maxGain;
    }
};

Best Time to Buy and Sell Stock - Unlimited Transactions

When multiple transactions are allowed, the maximum profit is simply the sum of all positive price deltas. Every upward slope in the price graph can be captured for profit.

#include <vector>

class StockTrader2 {
public:
    int maxUnlimitedProfit(std::vector<int>& priceHistory) {
        int totalYield = 0;
        for (size_t i = 1; i < priceHistory.size(); ++i) {
            if (priceHistory[i] > priceHistory[i - 1]) {
                totalYield += priceHistory[i] - priceHistory[i - 1];
            }
        }
        return totalYield;
    }
};

Best Time to Buy and Sell Stock - At Most Two Transactions

Limiting transactions to two requires tracking four states: the cost of the first purchase, the profit after the first sale, the cost of the second purchase (which deducts the first profit), and the final profit after the second sale. This state machine approach runs in O(n) time and O(1) space.

#include <vector>
#include <algorithm>
#include <climits>

class StockTrader3 {
public:
    int maxTwoTransactionsProfit(std::vector<int>& priceHistory) {
        int cost1 = INT_MAX, cost2 = INT_MAX;
        int yield1 = 0, yield2 = 0;
        
        for (int currentPrice : priceHistory) {
            cost1 = std::min(cost1, currentPrice);
            yield1 = std::max(yield1, currentPrice - cost1);
            cost2 = std::min(cost2, currentPrice - yield1);
            yield2 = std::max(yield2, currentPrice - cost2);
        }
        return yield2;
    }
};

Burst Balloons

The key to solving the balloon bursting problem is to think in reverse: instead of deciding which balloon to burst first, decide which balloon to burst last. By adding virtual balloons with a value of 1 at the boundaries, we can define memo[l][r] as the maximum coins obtained by bursting all balloons between l and r exclusively, assuming lastBurst is the final balloon popped in that range.

#include <vector>
#include <algorithm>

class BalloonBurst {
public:
    int computeMaxCoins(std::vector<int>& inputNums) {
        int n = inputNums.size();
        std::vector<int> extendedNums(n + 2, 1);
        for (int i = 1; i <= n; ++i) {
            extendedNums[i] = inputNums[i - 1];
        }
        
        std::vector<std::vector<int>> memo(n + 2, std::vector<int>(n + 2, 0));
        
        for (int segmentLen = 1; segmentLen <= n; ++segmentLen) {
            for (int l = 1; l <= n - segmentLen + 1; ++l) {
                int r = l + segmentLen - 1;
                for (int lastBurst = l; lastBurst <= r; ++lastBurst) {
                    int currentCoins = extendedNums[l - 1] * extendedNums[lastBurst] * extendedNums[r + 1];
                    memo[l][r] = std::max(memo[l][r], memo[l][lastBurst - 1] + currentCoins + memo[lastBurst + 1][r]);
                }
            }
        }
        return memo[1][n];
    }
};

Decode Ways

Decoding a string of digits is similar to climbing stairs (Fibonacci sequence), but with constraints. At each step, we must validate whether the single digit is non-zero and whether the two-digit combination forms a valid letter (between 10 and 26).

#include <string>
#include <vector>

class DecodeSolver {
public:
    int countValidDecodings(std::string encodedStr) {
        int len = encodedStr.length();
        if (len == 0 || encodedStr[0] == '0') return 0;
        
        std::vector<int> ways(len + 1, 0);
        ways[0] = 1; 
        ways[1] = 1;
        
        for (int i = 2; i <= len; ++i) {
            int singleDigit = encodedStr[i - 1] - '0';
            int doubleDigit = (encodedStr[i - 2] - '0') * 10 + singleDigit;
            
            if (singleDigit != 0) {
                ways[i] += ways[i - 1];
            }
            if (doubleDigit >= 10 && doubleDigit <= 26) {
                ways[i] += ways[i - 2];
            }
        }
        return ways[len];
    }
};

Counting Bits

To count the number of 1-bits for every integer from 0 to n efficiently, we can use dynamic programming with bit manipulation. The number of set bits in an integer i is equal to the number of set bits in i / 2 (which drops the least significant bit) plus the value of the least significant bit of i.

#include <vector>

class BitCounter {
public:
    std::vector<int> countSetBits(int n) {
        std::vector<int> bitCounts(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            bitCounts[i] = bitCounts[i >> 1] + (i & 1);
        }
        return bitCounts;
    }
};