DP - Decision Making (Stock)

[sync-by-unito[bot]]

DP for Stock Questions, Good explanations:

1. [Must Read] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems
2. [Good Read] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution

DP Patterns: https://leetcode.com/discuss/general-discussion/458695/Dynamic-Programming-Patterns https://leetcode.com/discuss/interview-question/778035/dynamic-programming-patterns

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

Q283, MoveZeros, Classic question to present thinking process:

1. Naive to do bubble sort, O(N^2)
2. Sliding window, but can't gurantee 0,0,0 count matches the following non-zero 2,3,4 for example.
3. Slow Fast pointers, find one item (slow_ptr is 0, fast_ptr is non-zero), then do swap, O(N), but swap and checking drag performance.
4. Slow Fast pointers, move all non-zero values to zero value ptr, O(N).
5. Find slow_ptr first to further enhance 4, like this:

//283. Move Zeroes [Easy] Classic question to present the thinking process.

class Solution_q283 { public: void moveZeroes(std::vector& nums) { int slow = 0, fast = 0, n = nums.size(); //step1. find the first '0' for the slow_ptr while (slow < n && nums[slow] != 0) ++slow;

    //step2. move all non-zero val to left.
    fast = slow + 1;
    while (fast < n) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
        }
        ++fast;
    }

    //step3. fill zero to the tail.
    while (slow < n) nums[slow++] = 0;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//121. Best Time to Buy and Sell Stock [Easy] //why this one may be a dynamic programming: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/39112/Why-is-this-problem-tagged-with-%22Dynamic-programming%22

1. Naive, check every number, and all numbers in the left hand side of it. O(N*N)
2. Sliding window, sort array and record their index, no necessary works
3. Traverse once, record min and calculate profit.

class Solution_q121 { public: int maxProfit(std::vector& prices) { int buy = INT32_MAX; int maxProfit = 0, n = prices.size();

    for(int p: prices){
        maxProfit = std::max(maxProfit, p-buy);
        buy = std::min(buy, p);
    }
    return maxProfit;

    /*int maxProfit = 0, buy = INT32_MAX, n = prices.size();
    for(int i=0; i<n; ++i){
        //Traverse the prices, preserves the min price we've seen.
        if(buy >= prices[i]){   //if smaller price is found, record it.
            buy = prices[i];
        }else{
            //calculate profit.
            maxProfit = std::max(maxProfit, prices[i] - buy);
        }
    }
    return maxProfit;*/
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//122. Best Time to Buy and Sell Stock II d - a = (b - a) + (c - b) + (d - c) 1, buy and then sell on the same day means doing nothing on the that day, before the day start, you have nothing, when the day ends, you have nothing 2, same goes for "sell and then buy on the same day", before the day start, you have an amount of money, when the day ends, you still have the same amount of money 3, so you can actually add the diff up

class Solution_q122 { public: int maxProfit(std::vector& prices) { int ret = 0; for (size_t p = 1; p < prices.size(); ++p) ret += std::max(prices[p] - prices[p - 1], 0); return ret; } };

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//123 or 188. Best Time to Buy and Sell Stock III/IV [Hard]

[MUST READ] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution

int maxProfit(int k_trans, std::vector& prices) { if (prices.empty()) return 0; std::vector min(k_trans + 1, prices[0]); std::vector dp(k_trans + 1, 0); for (int i = 1; i < prices.size(); ++i) { for (int k = 1; k <= k_trans; ++k) { min[k] = std::min(min[k], prices[i] - dp[k - 1]); dp[k] = std::max(dp[k], prices[i] - min[k]); } } return dp[k_trans]; }or

class Solution_q123 { public: int maxProfit(std::vector& prices) { int buy1 = INT32_MAX, buy2 = INT32_MAX; int maxProfit1 = 0, maxProfit2 = 0, n = prices.size();

    for(int p: prices){
        //buy2 try to use current price - profit1, for example if we earn $100 so far
        //today it's price is $300, we only need to "pay" additional $200 to buy it.
        maxProfit2 = std::max(maxProfit2, p - buy2);
        buy2 = std::min(buy2, p - maxProfit1);

        //buy1 always records the minimun buy point.
        //maxProfit1 is BY FAR the maximun profit.
        maxProfit1 = std::max(maxProfit1, p - buy1);  
        buy1 = std::min(buy1, p); 
    }     
    return maxProfit2;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

Classic: This follows the same recurrence relations: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/most-consistent-ways-of-dealing-with-the-series-of-stock-problems

//121. Best Time to Buy and Sell Stock [Easy] class Solution_q121 { public: int maxProfit(std::vector& prices) { int T_i10 = 0, T_i11 = INT32_MIN; for (const int& p : prices) { T_i10 = std::max(T_i10, T_i11 + p); T_i11 = std::max(T_i11, -p); } return T_i10; } };

//122. Best Time to Buy and Sell Stock II [Easy] class Solution_q122 { public: int maxProfit(std::vector& prices) { int T_i0 = 0, T_i1 = INT32_MIN;

    for (const int& p : prices) {
        T_i0 = std::max(T_i0, T_i1 + p);
        T_i1 = std::max(T_i1, T_i0 - p);
    }
    return T_i0;
}

};

//123. Best Time to Buy and Sell Stock III [Hard], DP class Solution_q123 { public: int maxProfit(std::vector& prices) { const int K = 2; std::vector T_i0(K + 1, 0), T_i1(K + 1, INT32_MIN); for (const int& p : prices) { for (int i = 2; i > 0; --i) { T_i0[i] = std::max(T_i0[i], T_i1[i] + p); T_i1[i] = std::max(T_i1[i], T_i0[i - 1] - p); } } return T_i0[K]; } };

//188. Best Time to Buy and Sell Stock IV [Hard] class Solution_q188 { public: int maxProfitForLargeK(std::vector& prices) { int T_i0 = 0, T_i1 = INT32_MIN; for (const int& p : prices) { T_i0 = std::max(T_i0, T_i1 + p); T_i1 = std::max(T_i1, T_i0 - p); } return T_i0; } };

//714. Best Time to Buy and Sell Stock with Transaction Fee [Med] class Solution_q714 { public: int maxProfit(std::vector& prices, int fee) { long T_i0 = 0, T_i1 = INT32_MIN; for (const int& p : prices) { T_i0 = std::max(T_i0, T_i1 + p - fee); T_i1 = std::max(T_i1, T_i0 - p); } return T_i0; } };

//309. Best Time to Buy and Sell Stock with Cooldown [Med] class Solution_q309 { public: int maxProfit(std::vector& prices) { int T_i0 = 0, T_i1 = INT32_MIN; int T_i0_pre = 0; for (const int& p : prices) { int T_i0_old = T_i0; T_i0 = std::max(T_i0, T_i1 + p); T_i1 = std::max(T_i1, T_i0_pre - p); T_i0_pre = T_i0_old; } return T_i0; } };