Dynamic Programming (DP)

Buy and Sell Stock

121 Best Time to Buy and Sell Stock

Base Case:
        int minPrice = prices[0];
        int maxProfit = 0;

Formula:
        for (auto i = 0; i < prices.size(); i++) {
            minPrice = min(minPrice, prices[i]);
            maxProfit = max(maxProfit, prices[i] - minPrice);
        }

122. Best Time to Buy and Sell Stock II

Greedily Add all the prices[i] - prices[i - 1] delta to the total profit if it is greater than zero (since we can complete as much transactions as we want and there is no transaction fees)

A slightly improvement is that, in a inner while loop, first record j = i as the starting price, while (i < N - 1 && prices[i] < prices[i +1]) we keep increase i, until it no longer holds. Then add the delta prices[i] - prices[j] to the total res. This is still O(N) time and O(1) space, but slightly less arithmetic operations.


309 Best Time to Buy and Sell Stock with Cooldown

buy[i]表示在第i天之前最后一个操作是买，此时的最大收益。
sell[i]表示在第i天之前最后一个操作是卖，此时的最大收益。
rest[i]表示在第i天之前最后一个操作是冷冻期，此时的最大收益。
我们写出递推式为：
 
buy[i]  = max(rest[i-1] - price, buy[i-1]) 
sell[i] = max(buy[i-1] + price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

53 Maximum Subarray  
Base Case: 
    int res = INT_MIN;
        int curSum = 0;

Formula:
        for (int i = 0; i < nums.size(); i++) {
            curSum = max(curSum + nums[i], nums[i]);
            res = max(curSum, res);
        }


70
    vector<int> DP(N,  0);
    DP[0] = 1;
    DP[1] = 2;

 DP[i] = min(DP[i - 1] , DP[i - 2] );   where i is from 2 to N - 1
746

vector<int> DP(N + 1, INT_MAX);

DP[i] denotes the minimum cost arrive on steps i (i = N, meaning top)
Base case:
               DP[0] = 0;
               DP[1] = 0;

 DP[i] = min(DP[i - 1] + cost[i - 1], DP[i - 2] + cost[i - 2]);   where i is from 2 to N

152 Maximum Product Subarray
 Base Case: 
        int res = nums[0];
        int minProd = nums[0];
        int maxProd = nums[0];
Formula:
        for (int i = 1; i < nums.size(); i++) {
            int tmp = minProd;
            minProd = min({sum[i], nums[i] * minProd, nums[i] * maxProd});
            maxProd = max({sums[i], nums[i] * maxProd, nums[i] * tmp});
            res = max(res, maxProd);
        }



303
  (1) Preprocressing prefixSums[0 ~ N] to save 0, nums[0], nums[0] + nums[1]...., nums[0] + .. nums[N - 1] in the NumArray constructor.

(2) When query, just return prefixSums[j + 1] - prefixSums[i];    



304 Range Sum Query 2D - Immutable
Slightly hard the 303,
here we should calculate  sums  as:
 sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + matrix[i][j];
where i : [0 ~ m - 1] and j: [0 ~ n - 1]

Sum region should return:
        return sums[r2 + 1][c2 + 1] - sums[r1][c2 + 1] - sums[r2 + 1][c1] + sums[r1][c1];

        (formula: sum(r2, c2) - sum(r1 - 1, c2) - sum(r2, c1 - 1) + sum(r1, c1))

 
338 Counting Bits 
  
//  i bin    '1'   i&(i-1)
//    0000    0
// -----------------------
//    0001    1    0000
// -----------------------
//    0010    1    0000
//    0011    2    0010
// -----------------------
//    0100    1    0000
//    0101    2    0100
//    0110    2    0100
//    0111    3    0110
// -----------------------
//    1000    1    0000
//    1001    2    1000
//    1010    2    1000
//    1011    3    1010
//    1100    2    1000
//    1101    3    1100
//    1110    3    1100
//    1111    4    1110
// 我们可以发现每个i值都是i&(i-1)对应的值加1，这样我们就可以写出代码如下
// Dp formula: dp[i] = dp[i & (i - 1)] + 1;
 
 vector<int> countBits(int num) {
        vector<int> res(num + 1, 0);
        for (int i = 1; i <= num; i++) 
           res[i] = res[i & (i - 1)] + 1; 
        
        return res;
    }


413 Arithmetic Slices
dp base:
     define an array vector<int> array dp and initialize all elements to 0

dp formula:
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {    dp[i] = dp[i - 1] + 1;    }

improvement:
use variable dp instead of O(N) array, but need to reset dp = 0 when there is
a dis-continuous point encountered.



String

 647 Palindromic Substrings   
(a) Brute Force:
The naive solution is O(N^3) which is simply, for loop each start position form (0 to n-1), and check each length of the sub string (from 1 to n) and check whether it is a palindrome string if so increase the counter by 1. Finally return the counter value.

(b) Expand around center (O(N^2))
Intuition
Let N be the length of the string. The middle of the palindrome could be in one of 2N - 1 positions: either at letter or between two letters.
For each center, let's count all the palindromes that have this center. Notice that if [a, b] is a palindromic interval (meaning S[a], S[a+1], ..., S[b] is a palindrome), then [a+1, b-1] is one too.
Algorithm
For each possible palindrome center, let's expand our candidate palindrome on the interval [left, right] as long as we can. The condition for expanding is left >= 0 and right < N and S[left] == S[right]. That means we want to count a new palindrome S[left], S[left+1], ..., S[right].

(c) There is a Manacher's O(N) algorithm (2*N in fact) I need to study some day.
https://leetcode.com/problems/palindromic-substrings/solution/

Define a 2-D dp array of bool, initialize all the n * n elements to false.
In a double for loop, where i is from n - 1 to 0 inclusive. And Inner loop
controller j is from i to n - 1 inclusive, if s[i] == s[j] and (j - i <= 1 || dp[i + 1][j - 1])
set dp[i][j] to true as well.  add dp[i][j] to the total number of palindrome count while
traversal.


dp[i][j] means whether s[i:j] is a palindrome
Base 1: dp[i][i] all true (single char is a palindrome, in in [0, n - 1])
Base 2: dp[i][i + 1] is true if s[i] == s[i + 1] (i in [0, n - 2])
dp formula:
 if (dp[i + 1][j - 1] && s[i] == s[j])
     dp[i][j] = true;
update longestBegin and maxLen accordingly whenever see a new palindrome. Traverse substring from short to long, this guarantees we get the longest substring in the end.
516

 vector<vector<int> > dp(n, vector<int>(n, 0));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i]  = 1; // Base case: single char parlindrome
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j])
                    // dp[i][j] is the longest Parlindrom Sequence length for s[i:j]
                    dp[i][j] = dp[i + 1][j - 1] + 2;  // dp formula 1
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); // dp formula 2
            }
        }
       
        return dp[0][n - 1];

Math
Base Case:
  vector<int> dp(10, 0);
        dp[0] = 1;
        dp[1] = 9;

DP formula:
        int res = dp[0] + dp[1];
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] * (11 - i);
            res += dp[i];
        }

return res;
       
Unique Paths / Minimum Sum in 2-D grid


62
   vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
        Base Case:
        dp[0][1] = 1; // crucial for correct answer
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // dp formula
            }
        }
       
        return dp[m][n];




63
 Similar to 62, except that dp formula need to reset to zero if
obstacleGrid[i - 1][j - 1] point is an obstacle.

               if (obstacleGrid[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else
                    dp[i][j] = 0; // obstacle, reset to 0

 64 Minimum Path Sum
  // dp[i][j] means minimum sum until point (i,j)
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = 0; // crucial for correct answer
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = grid[i - 1][j - 1] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
       
        return dp[m][n];
    }


House Rob Related:

198 House Robber    
 vector<int> dp(n + 1, 0);
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            // max of rob the ith house and not rob the ith house
            dp[i] = max(nums[i - 1] + dp[i - 2], dp[i - 1]); // nums is 0 indexed
        }
       
        return dp[n];


213 House Robber II
This can converted to problem 198, if we consider get the max of rob the first (n - 1) house or the last (n - 1) house. We don't have to literally create two sub-arrays, just use index to indicate the start and end of the sub-arrays is enough.


740
Delete and Earn    (convert to house rob)
 (1) Get the maximum value in the numbers array, say maxVal, and allocate an array with maxVal + 1 elements all initialized to 0, call it points array.
(2) Sum all the num values in the numbers array, and save the sum to points[num], i.e: points[num] = num + num + ... num (num * repeated time),
(3) Call house rob on points array to get the maximum points could  rob.


Trees
define dp[i] meaning the total number of Unique BST with i nodes.
Base Case:
dp[0] = dp[1] = 1;
DP formula:
dp[i] += dp[j] * dp[i - j - 1]       (where j in [0, i - 1], i in [2, n])


 377 Combination Sum IV
Define dp[i] is the total number of combinations sum to target i which could constructed from using all numbers 
 vector<int> dp(target + 1, 0);

        Base Case:
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (const auto& num : nums) {
                // dp formula:
                dp[i] += i >= num ? dp[i - num] : 0;
            }
        }
       
        return dp[target]; 


718 Maximum Length of Repeated Subarray
dp[i][j] means the maximum length of repeated subarray for optimal sub-problem A[i, m - 1] 
with B[j, n - 1]
Base Case: no
DP formula:
dp[i][j] = dp[i + 1][j + 1] + 1, if A[i] == B[j],
where i in [0, m - 1] and j in [0, n - 1]

 300 Longest Increasing Subsequence
 dp[i]: the size of longest increasing subsequence ending with nums[i]
 Base Case:
  dp[i] = 1, where i in [0, n - 1]
 dp formula:
  dp[i] = max(dp[j]) + 1 if nums[j] < nums[i], where i in [1, n - 1], j in [0, i - 1]

279 Perfect Squares
dp[i]: the least number of perfect square numbers which sum to i.
Base Case:
  dp[i * i] = 1; for i = 0 ~ sqrt(n)
DP formula:
dp[i] = min(dp[i - j^2] + 1) (j = 1 ~ i^0.5) 



416
  (1) Get the total sum of the whole array
  (2) If sum % 2 != 0, return false
  (3) Otherwise, target = sum >> 1;
  (4) define a vector<bool> dp(target + 1, false);
       dp[i] means whether there is a subset  of number sum to i in the array
       Base Case:
        dp[0] = true;
      DP formula:
       for (const auto& num : nums) {
            for (int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
       
        return dp[target];




120
Triangle    
Base case:
dp[j] = triangle[row - 1][j] for j = 0,1, ... row - 1
DP formula:
 dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
the min path value will be  dp[0] finally
O(N) space and O(N^2) time

523 Continuous Subarray Sum
同余定理（a % b == c % b, then b divides (a - c)
Here dp is use prefix sum to reduce time complixity from O(N^2) to O(N), also have to use a pre variable to
save the previous remainder seen, but only save it to the hashSet after one more loop to make sure only
sub-array has size >= 2 is considered. once seen the same  remainder again. Meaning find a sub-array which can
be divided by k.

Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more