Need help with a DP problem.
Difference between en1 and en2, changed 5 character(s)
**Problem link** — https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/↵

**Problem Description:** ↵

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.↵

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)↵

Return the maximum profit you can make.↵

**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.↵

**Note:**↵
0 < prices.length <= 50000; ↵
0 < prices[i] < 50000; ↵
0 <= fee < 50000.↵


**My Solution** : I have come up with a backtrack solution, which is working fine with smaller inputs, but gives TLE with  bigger inputs. I am unable to memoize it. Need Help !!!↵

What I am doing is, I am checking if the we have already purchased a share, If Yes, either we can sell the share now or later. If No, we either purchase it now or later. ↵


~
~~~~↵
class Solution↵
{↵
    public:↵
    ↵
    int solve (vector<int> &prices, bool hasPurchased, int lastPurchasedVal, int i, int fee)↵
    {↵
        if (i == prices.size()) return 0;↵
        ↵
       // if (dp[hasPurchased][i] != -1) return dp[hasPurchased][i];↵
        ↵
        if (hasPurchased)↵
        {↵
            int sold = INT_MIN;↵
            int profit = prices[i] - lastPurchasedVal - fee;↵
            if (profit > 0)↵
                sold = profit + solve (prices, !hasPurchased, 0, i+1, fee);↵
            int notsold = solve(prices, hasPurchased, lastPurchasedVal, i+2, fee);↵
            return  max(sold, notsold);↵
        }↵
        else↵
        {↵
            int purchased = solve (prices, !hasPurchased, prices[i], i+1, fee);↵
            int notPurchased = solve(prices, hasPurchased, lastPurchasedVal, i+1, fee);↵
            return  max(purchased, notPurchased);↵
        }       ↵
    }↵
    ↵
    int maxProfit(vector<int>& prices, int fee) ↵
    {↵
        //int dp[2][50001];↵
        //memset(dp, -1, sizeof dp);↵
        return solve (prices, false, 0, 0, fee);↵
    }↵
};↵
~~~~~↵


Thank you.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English haribhatt34 2018-11-21 14:59:00 5
en1 English haribhatt34 2018-11-21 14:57:34 2510 Initial revision (published)