My sky
My dream, my codes

Part 5 – Dynamic Programming – Troubleshooting backtracking algorithm

freewind
March 23, 2023
Algorithm

Introduction

In earlier post, Part 4 – Dynamic Programming – Iteration in Recurrence Relation – My sky (freewindcode.com) , backtracking algorithm has been used to implement build decision tree and apply top-down approach. The algorithm is hard to follow and debug because of the recursive calls. In this post, I show a case of myself struggling to correct my backtracking algorithm. In doing so, I show the exact part of the codes that perform:

  • forward movement and forward logic
  • backtracking movement and backtracking logic
  • rightward / horizontal movement/ going to next branch.

Employing a backtrack algorithm, we would have the following pseudocodes;

int  recursiveCall(inputArray, stateVariable){   
    // base case:
    if (stateVariable = someValue)
         return someValue;
    int someValueOfTheLevel;
    for (int i=0; i< inputArray.max(); i++){  // to traverse horizontally between branches
         // forward logic handled here:
         int valueOfChildNode = change (inputArray, inputArray[i+1])   // call change to go deeper, to child nodes.
         // child node returns value, backtracking logic is handled here.
         valueOfChildNode = doSomething; 
    }
    // backtracking from the last branch in the child level
    // this is when the parent node gets the result from all the child node's combined logic.
    // note the values different between stateVariable is of the parent node vs the value inputArray[i+1] at line  8, which is the stateVariable of child node.
    someValueOfTheLevel = valueOfChildNode; 
    return someValueOfTheLevel;  
}

The following diagram illustrates how the backtracking codes traverse the decision tree

In order to be able to debug problem in backtracking algorithm we need to know:

  • the expected values of state variables at each state or node.
  • which part of the codes would return from child nodes to parent nodes.
  • when the code reaches the last child node and traverse back to parent nodes

In addition, memoization is used to improve the speed of backtracking algorithm in such a way that not every branch is visited because some branches have the same pattern and returning data as the others. Choosing the appropriate dimension and data structure for the cache is important to efficiently optimized backtracking algorithm.

Sample problem Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Implementing top-down approach with backtracking algo + memoization

The following solution attempts to solve problem using backtracking algorithm.

  • each Node is a state that could be called via recursive call to return the number of coins that has been changed (added up from child node).
  • The state variables (first analysis)
    • the coin denominator or coinIndex in coin array
    • the remaining amount
  • Base cases
    • if remaining amount = 0: exact change was found, return 0 and backtrack to calculate the number coins
    • if remaining amount <0: no exact change was found, return INT_MAX. But in the end, return -1
  • Recurrence case:
    • if we take the coin denominator: then number of coin = 1 + numberOfCoinInNextTurn
    • if we dont take the coin denominator then number of coin = currentNumberOfCoin (nothing change).
    • the numberOfCoinInNextTurn is found by recursive call which goes deeper in child branch of the decision tree.
    • backtracking happens when the numberOfCoinInNextTurn returns result; the result is compared to parent node to find smaller value.
  • Memoization:
    • Normally, if we 2 state variables, we could simply use 2D array, each dimension representing a state variable
    • However, since the remaining amount could get below negative, whereas we cannot have negative index on an array, we have revise our state variables, and memoization cache data structure.
  • State Variables (optimized):
    • between, coin index and remaining amount, we see that the remaining amount is the more important state variable as it is unique. Let say, we have the coinList = {1,2,5} and the amount as 4. Using coin = 2 or coinIndex=1, we would have different remaining amount and different number of coins depending on our previous choice.
    • however, we cannot use vector as the data structure for cache as amount could go negative, while the vector index cannot. Thus we use map as a the data structure.

Below is the decision tree with sample test coins={1,2,5}, and amount = 4. Change(x,y) represents the call to recursive function int change(vector<int>& coins, int cointIndex, int amount) where x= coinIndex and y = amount. The boxes in same color indicate where cache value could be stored and retrieved.

Code

class Solution {
public:
    map<int, int> cache;
    // return number of coins after using the coin denomination and the remaining Amount
    int change(vector<int>& coins, int cointIndex, int amount){
        memoization:
        if (cache.find(amount) !=cache.end())
            return cache[amount];
        // base case:
        if (amount < 0)
            return INT_MAX;      // cannot exchange with exact coin, return an invalid result
        if (amount == 0){
            return 0;       
        }
        // recurrence case, run backtracking algorithm
        int  minNumberOfCoins = INT_MAX;
        for (int cointIndex=0; cointIndex < coins.size(); cointIndex++){
            int remainingAmount = amount - coins[cointIndex];
            // PROCEED TO NEXT TURN
            int numberOfCoinInNextTurn = change (coins, cointIndex, remainingAmount);       // proceed to next turn, take same coin denomination (go deeper in the same branch)  
            // ON BACKTRACKING, if child branch returns valid values, perform logic calculation  
            if (remainingAmount >= 0 && numberOfCoinInNextTurn != INT_MAX) {                                           
                minNumberOfCoins = min ( 1 + numberOfCoinInNextTurn,                       // this turn, take this coin denomination and in next turn, use the same denomination (go deeper in the same branch)
                                            minNumberOfCoins                 // dont use the same coin denomination this turn (go right to next branch)
                                        ) ;
            }    
        }
        cache[amount] = minNumberOfCoins;
        return minNumberOfCoins;
    }
    int coinChange(vector<int>& coins, int amount) {  
        int result = change(coins, 0, amount);
        return result == INT_MAX ? -1 : result ;      
    } 
};

Complexity analysis:

Time complexity of this algorithm is O(nmlogm) where n is the number of coin denominator and m is the amount.

The backtracking algorithm that includes for loop and recursive call inside the for loop is similar to the double for loop:

for (int cointIndex=0; cointIndex < coins.size(); cointIndex++){
    int numberOfCoinInNextTurn  = change (coins, cointIndex, remainingAmount);
}

// is similar to:

for (int cointIndex=0; cointIndex < coins.size(); cointIndex++){
    for (int j = cointIndex; j < someValue ; j++) {
    }
}
// the 'someValue' is actually defined by logic inside the recursive call, and when remainingAmount goes to zero.

Thus we can see that time complexity is O(n*m) where n is the coins.size() and m is the amount.

In addition, within the recursive call, since we implement map and call function find the check saved value, the find function itself runs log(m). Consequently, we have overall time complexity as O(nmlogm)

Bad Solution with bad backtracking logic

The below code is my first sloppy attempt which passed 31/189 test cases. As learning from failure is more helpful for future uses than just finding a single solution, I wrote this section to dedicate what I found from this bad implementation.

class Solution {
public:
    vector<vector<int>>cache; 
    // return number of coins after using the coin denomination and the remaining Amount
    int change(vector<int>& coins, int cointIndex, int amount){
        // base case:
        if (amount < 0)
            return INT_MAX;      // cannot exchange with exact coin, return an invalid result
        if (amount == 0){
            return 0;       
        }
        // memoization
        if (cache[cointIndex][amount] != INT_MAX){
            return cache[cointIndex][amount];
        }
        // recurrence case, run backtracking algorithm
        int  minNumberOfCoins = INT_MAX;
        for (int cointIndex=0; cointIndex < coins.size(); cointIndex++){
            int remainingAmount = amount - coins[cointIndex];
            // PROCEED TO NEXT TURN
            int numberOfCoinInNextTurn  = change (coins, cointIndex, remainingAmount);       // proceed to next turn, take same coin denomination (go deeper in the same branch)  
            // ON BACKTRACKING, if child branch returns valid values, perform logic calculation  
            if (numberOfCoinInNextTurn  != INT_MAX)                                            
                minNumberOfCoins = min ( 1 + numberOfCoinInNextTurn ,                       // this turn, take this coin denomination and in next turn, use the same denomination (go deeper in the same branch)
                                            minNumberOfCoins                 // dont use the same coin denomination this turn (go right to next branch)
                                        ) ;     
        }
        return cache[cointIndex][amount] = minNumberOfCoins;
    }
    int coinChange(vector<int>& coins, int amount) {         
        cache.resize(coins.size(), vector<int>(amount+1, INT_MAX));
        int result = change(coins, 0, amount);
        return result == INT_MAX ? -1 : result ;      
    }
};

The program has a few issues as below:

  • the memoization was actually not used! Memoization cache should be checked before anything else. In this program, the logic checks the remaining amount first and returns the number of coins. There are cases when the remaining amount be zero or negative, and could have been saved but not found from the cache.
  • the 2 state variables and 2D vector cache chosen are not suitable because we could have negative amount but cannot have negative index.
  • the condition if(numberOfCoinsNextTurn != INT_MAX) is problematic
    • It was intentional that if the number of coins returns from child leaf is not zero, if(numberOfCoinsNextTurn !=0), then we make further recursive call, going deeper into the decision tree. However, the condition is problematic, because, if remaining amount <0, then we assign the number of coins INT_MAX. There will cause compile error when we have 1+INT_MAX.
    • if(numberOfCoinsNextTurn != INT_MAX) would fix the overflow issue that if(nextTurn !=0) causes. However, it doesn't distinguish between a saved result in the cache and an empty cache result. The cache was initialized with INT_MAX value. Thus, had cache used only 1 dimension with proper choice of state variable, this logic wouldn't help at all.
    • Thus the correct logic should have been if(remainingAmount>0) or something else!

Version 1: fix backtracking logic

The following has the fix if(remainingAmound >0), but it is still problematic. The problem has overflow issue.

class Solution {
public:
    // return number of coins after using the coin denomination and the remaining Amount
    int change(vector<int>& coins, int cointIndex, int amount){
        cout<<"**FORWARD to Node coints: "<<coins[cointIndex]<<" remaining amount "<<amount<<"**"<<endl;
        // base case:
        if (amount < 0)
            return -1;      // cannot exchange with exact coin, return an invalid result
        if (amount == 0){
            return 0;       
        }
        // recurrence case, run backtracking algorithm
        int  minNumberOfCoins = INT_MAX;
        for (int cointIndex=0; cointIndex < coins.size(); cointIndex++){
            int remainingAmount = amount - coins[cointIndex];
            // PROCEED TO NEXT TURN
            int numberOfCoinInNextTurn = change (coins, cointIndex, remainingAmount);       // proceed to next turn, take same coin denomination (go deeper in the same branch)  
            cout<<"     BACKTRACKING:child node returns result to current node "<<numberOfCoinInNextTurn<<" Node remaining amount is "<<remainingAmount<<" coin is "<<coins[cointIndex]<<endl;  
            // ON BACKTRACKING, if child branch returns valid values, perform logic calculation  
            if (remainingAmount > 0 ) {                                           
                minNumberOfCoins = min ( 1 + numberOfCoinInNextTurn,                       // this turn, take this coin denomination and in next turn, use the same denomination (go deeper in the same branch)
                                            minNumberOfCoins                 // dont use the same coin denomination this turn (go right to next branch)
                                        ) ;
            cout<<"     minNumberOfCoins"<<minNumberOfCoins<<endl; 
            }    
        }
        cout<<"**EXIT LAST BRANCH in level, backtracking to higher level, minNumberOfcoins from child level:"<<minNumberOfCoins<<". Parent node is at coin: "<<coins[cointIndex]<<" remaining amount: "<<amount<<" **"<<endl;
        return minNumberOfCoins;
    }
    int coinChange(vector<int>& coins, int amount) {   
        int result = change(coins, 0, amount);
        return result == -1 ? -1 : result ;      
    } 
};
  • the condition if (remainingAmount>0) is problematic and causes runtime failure in backtracking algorithm
    • Let say we choose coin=1 and remainingAmount = 0. We assign the value 0 to child node and backtrack. if(remainingAmound >0) will prevent going further down the decision tree. However, it also prevents comparing to get the min value, returned by change(0,0). Thus there is no comparison minNumberOfCoins = min ( 1 + numberOfCoinInNextTurn, minNumberOfCoins ) = min( 0 , INT_MAX).
    • Let say we choose coin=5 and remainingAmount = -4 . We assign the value INT_MAX to child node, and backtrack. if(remainingAmound >0) will prevent going further down the decision tree. However, it also prevents comparing to get the min value, returned by change(0,0) when we use coin 1, and get remainingAmount=0 !!!
    • Likewise, all 3 child nodes where {coin=1, remainingAmount=0}, {coin=2,remainingAmount=-1}, {coin=5, remainingAmount=-4} all returns INT_MAX. No comparison is invoked to returns the parent node {Coin1, remainingAmount=1} the expected value 0 but INT_MAX.

The following diagrams illustrates the issue

Running the above program returns the following logs. It indicates that at the node when then coin=1, remainingAmount=1, instead of getting return number of coins from child node as 0, we have INT_MAX.

**FORWARD to Node coints: 1 remaining amount 4**
**FORWARD to Node coints: 1 remaining amount 3**
**FORWARD to Node coints: 1 remaining amount 2**
**FORWARD to Node coints: 1 remaining amount 1**
**FORWARD to Node coints: 1 remaining amount 0**
     BACKTRACKING:child node returns result to current node 0 Node remaining amount is 0 coin is 1
**FORWARD to Node coints: 2 remaining amount -1**
     BACKTRACKING:child node returns result to current node -1 Node remaining amount is -1 coin is 2
**FORWARD to Node coints: 5 remaining amount -4**
     BACKTRACKING:child node returns result to current node -1 Node remaining amount is -4 coin is 5
**EXIT LAST BRANCH in level, backtracking to higher level, minNumberOfcoins from child level:2147483647. Parent node is at coin: 1 remaining amount: 1 **
     BACKTRACKING:child node returns result to current node 2147483647 Node remaining amount is 1 coin is 1

The logs indicates that value INT_MAX was returned to parent node {Coin 1, remain 1} instead of the expected value 0.

Version 2: further fixes on backtracking logic

Now we fix the condition with if(remainingAmount>=0), there is still overflow issue, and harder to troubleshoot, because it happens much later in the decision tree. I add some more logs to help with troubleshooting and tracing the backtracking flow.

class Solution {
public:
    // return number of coins after using the coin denomination and the remaining Amount
    int change(vector<int>& coins, int cointIndex, int amount){
        cout<<"**FORWARD to Node coints: "<<coins[cointIndex]<<" remaining amount "<<amount<<"**"<<endl;
        // base case:
        if (amount < 0)
            return -1;      // cannot exchange with exact coin, return an invalid result
        if (amount == 0){
            return 0;       
        }
        // recurrence case, run backtracking algorithm
        int  minNumberOfCoins = INT_MAX;
        for (int cointIndex=0; cointIndex < coins.size(); cointIndex++){
            int remainingAmount = amount - coins[cointIndex];
            // PROCEED TO NEXT TURN
            int numberOfCoinInNextTurn = change (coins, cointIndex, remainingAmount);       // proceed to next turn, take same coin denomination (go deeper in the same branch)  
            cout<<"     BACKTRACKING:child node returns result to current node "<<numberOfCoinInNextTurn<<" Node remaining amount is "<<remainingAmount<<" coin is "<<coins[cointIndex]<<endl;  
            // ON BACKTRACKING, if child branch returns valid values, perform logic calculation  
            if (remainingAmount >= 0 ) {                                           
                minNumberOfCoins = min ( 1 + numberOfCoinInNextTurn,                       // this turn, take this coin denomination and in next turn, use the same denomination (go deeper in the same branch)
                                            minNumberOfCoins                 // dont use the same coin denomination this turn (go right to next branch)
                                        ) ;
            cout<<"     minNumberOfCoins"<<minNumberOfCoins<<endl; 
            }    
        }
        cout<<"**EXIT LAST BRANCH in level, backtracking to higher level, minNumberOfcoins from child level:"<<minNumberOfCoins<<". Parent node is at coin: "<<coins[cointIndex]<<" remaining amount: "<<amount<<" **"<<endl;
        return minNumberOfCoins;
    }
    int coinChange(vector<int>& coins, int amount) {   
        int result = change(coins, 0, amount);
        return result == -1 ? -1 : result ;      
    } 
};

This issue is much easier recognized with test case coins=[2] and amount = 3:

It turns out that the issue is similar, while the very last child node calculates to INT_MAX when remainingAmount < 0. Backtracking logic, if(remainingAmount>=0), at parent node kicks in because we go back to previous node where the remainingAmount is greater than zero.

**FORWARD to Node coints: 2 remaining amount 3**
**FORWARD to Node coints: 2 remaining amount 1**
**FORWARD to Node coints: 2 remaining amount -1**
     BACKTRACKING:child node returns result to current node -1 Node remaining amount is -1 coin is 2
**EXIT LAST BRANCH in level, backtracking to higher level, minNumberOfcoins from child level:2147483647. Parent node is at coin: 2 remaining amount: 1 **
     BACKTRACKING:child node returns result to current node 2147483647 Node remaining amount is 1 coin is 2

The program could then be fixed with additional logic: 

if (remainingAmount >= 0 && nextTurn != INT_MAX)

The following is a cleaner fix of the above changes. Instead of using the above condition, we implement if (numberOfCoinInNextTurn != -1).

class Solution {
public:

    map<int, int> cache;

    int coinChange(vector<int>& coins, int amount) {
        if (cache.find(amount) != cache.end()) 
            return cache[amount];
        if (!amount) 
            return 0;
        if (amount < 0) 
            return -1;
        int fewstQuantity = INT_MAX;
        for (auto coin : coins) {
            int numberOfCoinInNextTurn = coinChange(coins, amount - coin);
            // Check whether or not can make up the change
            if (numberOfCoinInNextTurn != -1){
                numberOfCoinInNextTurn++;
                fewstQuantity = min(fewstQuantity, numberOfCoinInNextTurn); 
            }
        }
        cache[amount] = fewstQuantity == INT_MAX ? -1 : fewstQuantity;
        return cache[amount];
    }
};

Sample problem: Best time to Buy/Sell stocks with Transaction Fees

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Constraints:
  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= fee < 5 * 104

In the below sections, I details many errors and fix versions that I have made. If readers want only the the correct backtracking solution, please check out version 5.

The first 4 versions details a backtracking solution with an imperfect decision tree base on analysis on base condition and state variables. Backtracking logic was buggy and fixed. However, because of the bad decision tree, the algorithm has high time complexity.

In fix version 5, a completely different decision tree is draw, and the corresponding backtracking algorithm is simpler, and faster.

Bad solution

For this approach, I define the following:

  • State: the single trade date that returns the profit from that day to the end.
  • State variables:
    • Buy/Sell: the first trade could no trade or must be a Buy trade.
    • trade date: starting from any index of prices array.
    • price of trade date, and is used to calculate base condition.
  • Base condition:
    • if trade is buy: return -prices[tradeDate]
    • if trade is sell: return prices[tradeDate]+ fee
  • Recursive condition:
    • intuitively we have the profit on each day is calculated as currDailyProfit + maxNextDayProfit

In this sample problem, I describe all the mistakes that I have taken. The mistakes are about making wrong transitional equation, or making bad recursive condition.

Version 1: Fix failure to update current node value

In section 1, I found a bug in the forward condition, the logic that allows me to go deeper to child nodes of the decision tree.

In this problem, I analyze another bug due to bad transitional equation. 

class Solution {
public:
    int transactionFee;
    int dailyProfit(vector<int>&prices, int dayTrade, bool sell){
        cout<<"dayTrade="<<dayTrade<<" sell="<<sell<<" price="<<prices[dayTrade]<<endl;
        //base case:
        if (dayTrade == prices.size()-1){
            if (sell == true)
                return prices[dayTrade] - 2;
            else
                return -prices[dayTrade];
        }
        int currDay = 0;
        for (int day = dayTrade+1; day<prices.size(); day++)
            if (sell == false){
                // FORWARD LOGIC:
                int nextDay = dailyProfit(prices, day, true);
                // BACKTRACKING LOGIC: 
                cout<<"     profit in (SELL) child node is "<<nextDay<<" for day="<<day<<"at price="<<prices[day]<<endl;
                cout<<"     profit in (BUY) curr node is "<<currDay<<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
                currDay = max (currDay, currDay + nextDay);
                cout<<"     max profit in (BUY) curr node "<<currDay<<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
            }
            else{
                // FORWARD LOGIC
                int nextDay = dailyProfit(prices, day, false);

                // BACKTRACKING LOGIC: 
                cout<<"     profit in (BUY) child node is "<<nextDay<<" for day="<<day<<"at price="<<prices[day]<<endl;
                cout<<"     profit in (SELL) curr node is "<<currDay<<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
                currDay = max (currDay, currDay + nextDay);      
                cout<<"     max profit in curr SELL node is"<<currDay<<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
            }
        cout<<"reaching last node in same level, return maxProfit to parent node, maxProfit="<<currDay<<" for day="<<dayTrade<<"sell="<<sell<<" at price="<<prices[dayTrade]<<endl;
        return currDay;    
    }
    int maxProfit(vector<int>& prices, int fee) {
        transactionFee = fee;
        return dailyProfit(prices, 0, false);
    }
};

Output: using the test value prices={1,3,2,8} and fee=2, we have the following logs:

dayTrade=0 sell=0 price=1
dayTrade=1 sell=1 price=3
dayTrade=2 sell=0 price=2
dayTrade=3 sell=1 price=8
     profit in (SELL) child node is 6 for day=3at price=8
     profit in (BUY) curr node is 0 for day=2at price=2     //expect value=2
     max profit in (BUY) curr node 6 for day=2at price=2
reaching last node in same level, return maxProfit to parent node, maxProfit=6 for day=2sell=0 at price=2
     profit in (BUY) child node is 6 for day=2at price=2
     profit in (SELL) curr node is 0 for day=1at price=3    //expect value=3-2=1
     max profit in curr SELL node is6 for day=1at price=3

Consider each node is a state, that has 2 state variables: dayTrade and the price[dayTrade]. Each day also has option as Buy or Sell. I denote the node as: {Buy: price[dayTrade], dayTrade}.

The profit from each trade day could be calculated from child nodes to parent nodes: 

{Buy:  8, 3} = -8                  // when we buy, subtract money
{Sell: 8, 3} =  8-2 = 6            // when we sell, add the money earn
{Buy:  2, 2} = -2+(8-2) = 4   
{Sell: 3, 1} =  max [(3-2)+(-2+(8-2))] vs  [(3-2)+(-8)] = 5

The following diagram illustrates the above calculation:

Thus, it was tempted to come up with the general transitional equation: 

dailyProfit = currentDay + nextDay

When I have a parent node that splits to multiple child nodes, on backtracking logic, I use comparison:

maxDailyProfit = max (maxDailyProfit , maxDailyProfit + nextDay)

However, in my codes, I have currDay = 0, hence I actually just performed comparison: 

maxDailyProfit = max (0 , 0 + nextDay) = nextDay

Version 2: Fix incorrect transitional equation to compare the return values of child nodes.

I attempted to initialize the currentDay with the following condition in each for loop iteration

for (int day = dayTrade+1, day<prices.size(); day++){        
    int currDay;
    if (sell == true)
        currDay = prices[dayTrade] - 2;
    else
        currDay = -prices[dayTrade];
}

Running the above program, I have the output:

dayTrade=0 sell=0 price=1
dayTrade=1 sell=1 price=3
dayTrade=2 sell=0 price=2
dayTrade=3 sell=1 price=8
     profit in (SELL) child node is 6 for day=3at price=8
     profit in (BUY) curr node is -2 for day=2at price=2
     max profit in (BUY) curr node 4 for day=2at price=2
reaching last node in same level, return maxProfit to parent node, maxProfit=4 for day=2sell=0 at price=2
     profit in (BUY) child node is 4 for day=2at price=2
     profit in (SELL) curr node is 1 for day=1at price=3
     max profit in curr SELL node is5 for day=1at price=3    // something wrong here but was not showed on log  
dayTrade=3 sell=0 price=8
........ // some more logs
dayTrade=3 sell=1 price=8
     profit in (SELL) child node is 6 for day=3at price=8
     profit in (BUY) curr node is 4 for day=0at price=1
     max profit in (BUY) curr node 10 for day=0at price=1     // WRONG HERE
reaching last node in same level, return maxProfit to parent node, maxProfit=10 for day=0sell=0 at price=1

It turns out that the following transitional equation on backtracking logic is not right.

currDay = max (currDay, currDay + nextDay);

It is wrong bacuase of the addition currDay + nextDay used in the comparison. currDay in this case would be the value of child node in previous branch added with the value of current node. In other words, I have compared between:
other_branch_child_node+ current_node

vs

other_branch_child_node+ current_node + current_node + this_branch_child_node

whereas I want to compare

other_branch_child_node+ current_node

vs

this_branch_child_node + current_node

It could be explained with the following graph:

Suppose we sell on day 2 with price=3, we may have 2 options to buy, with price =2 or price =8. The maximum profit earned on day 2 is dependent on the maximum profit returned from next day trades.

For the above set of inputs, we are supposed to compared between: [(3-2) + (-2) +(8-2)] vs [(3-2) + (8-2)]. But the buggy codes compares: [(3-2) + (-2) +(8-2)] vs [(3-2) + (-2) +(8-2) + (8-2)]

I fix the bug with the following general transitional equations to compares only the values returns from the child nodes:

maxDailyProfit = currDayProfit + maxNextDayProfit;
maxNextDayProfit = max(profitFromLeftBranch, profitFromRightBranch)
class Solution {
public:
    int transactionFee;
    int dailyProfit(vector<int>&prices, int dayTrade, bool sell){
        cout<<"dayTrade="<<dayTrade<<" sell="<<sell<<" price="<<prices[dayTrade]<<endl;
        //base case:
        if (dayTrade == prices.size()-1){
            if (sell == true)
                return prices[dayTrade] - transactionFee;
            else
                return -prices[dayTrade];
        }
        int maxNextDayProfit = 0;
        int maxDailyProfit =0;
        for (int day = dayTrade+1; day<prices.size(); day++)
            if (sell == false){
                // FORWARD LOGIC:
                int currDay = -prices[dayTrade];
                int nextDay = dailyProfit(prices, day, true);
                // BACKTRACKING LOGIC: 
                cout<<"     profit in (SELL) child node is "<<nextDay<<" for day="<<day<<"at price="<<prices[day]<<endl;
                cout<<"     profit in (BUY) curr node is "<<currDay<<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
                maxNextDayProfit = max(maxNextDayProfit, nextDay);
                cout<<"     maxProfit returns from child node "<<maxNextDayProfit<<endl;
                maxDailyProfit  = currDay + maxNextDayProfit;
                cout<<"     max profit in (BUY) curr node "<<maxDailyProfit <<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
            }
            else{
                // FORWARD LOGIC
                int nextDay = dailyProfit(prices, day, false);
                int currDay = prices[dayTrade] - transactionFee;
                // BACKTRACKING LOGIC: 
                cout<<"     profit in (BUY) child node is "<<nextDay<<" for day="<<day<<"at price="<<prices[day]<<endl;
                cout<<"     profit in (SELL) curr node is "<<currDay<<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
                maxNextDayProfit = max(maxNextDayProfit, nextDay);
                cout<<"     maxProfit returns from child node "<<maxNextDayProfit<<endl;
                maxDailyProfit  = currDay + maxNextDayProfit;   
                cout<<"     max profit in curr SELL node is"<<maxDailyProfit <<" for day="<<dayTrade<<"at price="<<prices[dayTrade]<<endl;
            }
        cout<<"reaching last node in same level, update maxProfit to parent node, maxProfit="<<maxDailyProfit <<" for day="<<dayTrade<<"sell="<<sell<<" at price="<<prices[dayTrade]<<endl;
        return maxDailyProfit ;    
    }
    int maxProfit(vector<int>& prices, int fee) {
        transactionFee = fee;
        return dailyProfit(prices, 0, false);
    }
};

Version 3: Fix bug failure to consider edge cases where there is no trade.

In Version 1, I coded as following, and it was wrong because it fails to update trade on current day

maxDailyProfit = max (maxDailyProfit , 0 + nextDay)

In Version 2, I have the following transitional equation, which compares to max profits returned from child nodes (next day trade) and add that to the currentDayProfit.

maxNextDayProfit = max (maxNextDayProfit  , nextDayProfit)
maxDailyProfit= currDayProfit + maxNextDayProfit

However it is still sufficient because it assumes we always make a trade on current by assigning currDayProfit with a Buy or Sell value in each for loop iteration. What happen it we have a data set that only have decreasing stock price value. In that case, making no trade and keep profit at zero is the best action. The following diagram illustrates the scenario with sample input prices={9,2}, fee=:

Thus we should add another comparison in the following transitional equation:

maxNextDayProfit = max (maxNextDayProfit , nextDayProfit)
maxDailyProfit  = max(maxDailyProfit, currDay + maxNextDayProfit)

Both maxNextDayProfit, and maxDailyProfit are declared and initialized to zero outside the for loop.

Furthermore, if there is only one day to trade, prices.size() = 1, it is best not doing any trade at all.

Code:

class Solution {
public:
    int transactionFee;
    int dailyProfit(vector<int>&prices, int dayTrade, bool sell){
        //base case:
        if (dayTrade == prices.size()-1){
            if (sell == true)
                return prices[dayTrade] - transactionFee;
            else
                return -prices[dayTrade];
        }
        int maxNextDayProfit = 0;
        int maxDailyProfit =0;
        for (int day = dayTrade+1; day<prices.size(); day++){
            if (sell == false){
                // FORWARD LOGIC:
                int currDay = -prices[dayTrade];
                int nextDay = dailyProfit(prices, day, true);
                // BACKTRACKING LOGIC: 
                maxNextDayProfit = max(maxNextDayProfit, nextDay);
                // maxDailyProfit  = currDay + maxNextDayProfit;
                maxDailyProfit  = max(maxDailyProfit, currDay + maxNextDayProfit); 
            }
            else{
                // FORWARD LOGIC
                int currDay = prices[dayTrade] - transactionFee;
                int nextDay = dailyProfit(prices, day, false);
                // BACKTRACKING LOGIC: 
                maxNextDayProfit = max(maxNextDayProfit, nextDay);
                maxDailyProfit  = max(maxDailyProfit, currDay + maxNextDayProfit); 
            }
        }
        return maxDailyProfit ;    
    }
    int maxProfit(vector<int>& prices, int fee) {
        transactionFee = fee;
        if (prices.size() == 1)
            return 0;
        return dailyProfit(prices, 0, false);
    }
};

Version 4: Fix failure to go to next branch in initial condition.

Note that the first sample problem didn't have special case like this problem. Given an array of input, for the first problem, we can take the first value of the input and start the recursive call. It is because, the problem gives us a set of coin denomination, and we have to use every value to exchange for a certain amount. Therefore, we call the recursive function to solve our problem in 1 turn:

int result = change(coins, 0, amount);
return result == -1 ? -1 : result ;

However, for this problem, since it is a trading problem with the option of skipping trades, we could have our first trade with prices[0], or prices[1] or prices[100]. In other words, the single call to recursive function and calculate the result is not sufficient.

return dailyProfit(prices, 0, false);

The following image illustrate the error:

Thus, modifying the maxProfit function as below is required: 

int maxProfit(vector<int>& prices, int fee) {
        transactionFee = fee;
        if (prices.size() == 1)
            return 0;
        int result=0;
        for (int day = 0; day< prices.size(); day++){
            result = max(result,dailyProfit(prices, day, false));
        }
        return result;
}

Version 4: Add Memoization

We have the following state variables:

  • trade date
  • price on the trade date
  • the trade as Buy or Sell

Although, I have drawn decision trees where each node or trade is identified by the price and trade visualize the decision tree easier, the nodes are actually identified by only trade date and trade.

Therefore, the memoization cache should be 2D and the dimensions represent trade date and trade.

Code: 

class Solution {
public:
    int transactionFee;
    vector<vector<int>> cache;
    int dailyProfit(vector<int>&prices, int dayTrade, bool sell){
        //memoization:
        if (cache[dayTrade][sell] != -1){
            cout<<"Sell: "<<sell<<" dayTrade "<<dayTrade<<" price "<<prices[dayTrade]<<endl;
            return cache[dayTrade][sell];
        }
        //base case:
        if (dayTrade == prices.size()-1){
            if (sell == true)
                return prices[dayTrade] - transactionFee;
            else
                return -prices[dayTrade];
        }
        int maxNextDayProfit = 0;
        int maxDailyProfit =0;
        for (int day = dayTrade+1; day<prices.size(); day++){
            if (sell == false){
                // FORWARD LOGIC:
                int currDay = -prices[dayTrade];
                int nextDay = dailyProfit(prices, day, true);
                // BACKTRACKING LOGIC: 
                maxNextDayProfit = max(maxNextDayProfit, nextDay);
                maxDailyProfit  = max(maxDailyProfit, currDay + maxNextDayProfit); 
            }
            else{
                // FORWARD LOGIC
                int currDay = prices[dayTrade] - transactionFee;
                int nextDay = dailyProfit(prices, day, false);
                // BACKTRACKING LOGIC: 
                maxNextDayProfit = max(maxNextDayProfit, nextDay);
                maxDailyProfit  = max(maxDailyProfit, currDay + maxNextDayProfit); 
            }
        }
        return cache[dayTrade][sell]=maxDailyProfit ;
    }
    int maxProfit(vector<int>& prices, int fee) {
        transactionFee = fee;
        cache.resize(50000+1, vector<int>(2,-1));
        if (prices.size() == 1)
            return 0;
        int result=0;
        for (int day = 0; day< prices.size(); day++){
            int x = dailyProfit(prices, day, false);
            result = max(result,x);   
        }
        return result;
    }
};
Time Complexity:

Backtracking algorithm is slow, complicating and hard to debug. The above solution would have time complexity as O(n2). The outer for loop and recursive call to dailyProfit function could be understood as a double for loop: 

for (int day = 0; day< prices.size(); day++){
    for (int nextTrade = day+1; day< prices.size(); day++){
        // processing forward logic
    }
    // processing backtracking logic   
}

The number of time the codes would loop through all the logics is the sum of:

 (N (N + 1)) / 2 = (N^2 / 2) + (N / 2) where N = prices.size()

This problem needs a better algorithm to solve. In fact, it could be solved with time complexity as O(n).

Version 5: Improving complexity of backtracking algorithm by a different decision tree.

To improve time complexity, a different decision tree is considered.

  • state: a single trading date that returns values of the trades from day i to day n.
  • state variables:
    • trade type: Buy or Sell or Hold that effects the logic calculation. Price is no longer a state variable. Each node on the decision tree has 2 branches, corresponding to Buy/Sell or Hold (no trade).
    • day: from below decision tree, each day would be corresponding to a "level"
  • Base condition:
    • when day>= prices.size(), return 0.

The following diagram illustrates the decision tree which is completely different from above solution's. Each node now has only 2 branches. Trade (buy/sell) and Hold. The next state will have status buy/sell or hold.

Code:

class Solution {
public:
    int transactionFee;
    vector<vector<int>> cache;
    int dailyProfit(vector<int>&prices, int tradeDate, bool sell){
        // cout<<"Sell: "<<sell<<" dayTrade "<<tradeDate<<endl;
        //base case:
        if (tradeDate == prices.size()){
            return 0;
        }        

        //memoization:
        if (cache[tradeDate][sell] != -1){        
            return cache[tradeDate][sell];
        }     

        int maxDailyProfit =0;

        if (sell == false){  
            // FORWARD LOGIC:
            int currDay = -prices[tradeDate];
            int nextDayBuy = dailyProfit(prices, tradeDate+1, false);
            int nextDaySell = dailyProfit(prices, tradeDate+1, true);
            // BACKTRACKING LOGIC:
            int hold = 0  + nextDayBuy;
            int trade = currDay + nextDaySell; 
            maxDailyProfit = max (hold, trade); 
        }
        else{
            // FORWARD LOGIC
            int currDay = prices[tradeDate] - transactionFee;
            int nextDayBuy = dailyProfit(prices, tradeDate+1, false);
            int nextDaySell = dailyProfit(prices, tradeDate+1, true);
            // BACKTRACKING LOGIC: 
            int hold = 0  + nextDaySell;
            int trade = currDay + nextDayBuy; 
            maxDailyProfit = max (hold, trade); 
        }

        return cache[tradeDate][sell]=maxDailyProfit ;
    }
    int maxProfit(vector<int>& prices, int fee) {
        transactionFee = fee;
        cache.resize(prices.size(), vector<int>(2,-1));
        if (prices.size() == 1)
            return 0;
        return dailyProfit(prices, 0, false);
    }
};

Time complexity:

From the decision tree, we have the total number of outcomes = total number of branches = n x 2. Thus the complexity is O(n).

References:

This analysis of the decision trees, where each node status is Buy/Sell/Hold offers hints on another approach to solve this type problem. It uses State Machine.

🔖Tags: backtracking C++ DP
Share on Facebook
Share on Twitter

Leave a Reply

Your email address will not be published. Required fields are marked *