Dynamic Programming

There are three steps involved in solving a problem by dynamic programming:

  1. Formulate the answer as a recurrence relation or recursive algorithm.
  2. Show that the number of different parameter values taken on by your recurrence bounded by a (hopefully small) polynomial.
  3. Specify an order of evaluation for the recurrence so the partial results you need are always available when you need them.

longest increasing sequence

longest increasing sequence

partition problem

partition problem

traveler problem

traveler problem

pattern

this one describe the specific action at the time point of i,

Robber // leetcode 198

public int rob(int[] nums) {
    if (nums == null || nums.length < 1) return 0;
    if (nums.length < 2) return nums[0];
 
    int[] rob = new int[nums.length];
    int[] rest = new int[nums.length];
 
    rob[0] = nums[0];
    rest[0] = 0;
 
    for (int i=1; i<nums.length; i++) {
      rob[i] = Math.max(i >=2 ? rob[i-2] : 0, rest[i-1] + nums[i]);
      rest[i] = Math.max(rest[i-1], rob[i-1]);
    }
 
    return Math.max(rob[nums.length-1], rest[nums.length-1]) ;
  }

LIS // leetcode 300

 public int lengthOfLIS2(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] use = new int[nums.length];
    int[] idle = new int[nums.length];
 
    use[0] = 1;
    idle[0] = 0;
 
    for(int i=1; i< nums.length; i++) {
      idle[i] = Math.max(idle[i-1], use[i-1]);
      int v = 1;
      for (int j=i-1; j>=0; j--) {
        if (nums[i] > nums[j]) {
          v = Math.max(v, use[j] + 1);
        }
      }
      use[i] = v;
    }
 
    return Math.max(use[nums.length-1], idle[nums.length-1]);
  }

last action seen so far

stock leetcode 744

// https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108871/2-solutions-2-states-DP-solutions-clear-explanation!

(1) buy status:
buy[i] represents the max profit at day i in buy status, given that the last action you took is a buy action at day K, where K<=i.
And you have the right to sell at day i+1, or do nothing.
(2) sell status:
sell[i] represents the max profit at day i in sell status, given that the last action you took is a sell action at day K, where K<=i.
And you have the right to buy at day i+1, or do nothing.

Let's walk through from base case.

Base case:
We can start from buy status, which means we buy stock at day 0.
buy[0]=-prices[0];
Or we can start from sell status, which means we sell stock at day 0. Given that we don't have any stock at hand in day 0, we set sell status to be 0.
sell[0]=0;

public int maxProfit(int[] prices, int fee) {
    if (prices.length <= 1) return 0;
    int days = prices.length, buy[] = new int[days], sell[] = new int[days];
    buy[0]=-prices[0];
    for (int i = 1; i<days; i++) {
      buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]); // keep the same as day i-1, or buy from sell status at day i-1
      sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee); // keep the same as day i-1, or sell from buy status at day i-1
    }
    return sell[days - 1];
  }

generic dp

LIS // leetcode 300

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
 
    int[] dp = new int[nums.length];
 
    // dp[i] = dp[j] + 1 if (nums[j] < nums[i]) for 0 =< j < i;
 
    int max = 0;
    dp[0] = 1;
    for (int i=1; i<nums.length; i++) {
      dp[i] = 1;
      for (int j=0; j<i; j++) {
        if (nums[j] < nums[i] && (dp[j] + 1) > dp[i]) {
          dp[i] = dp[j] + 1;
        }
      }
      max = Math.max(max, dp[i]);
    }
 
    return max;
  }

stock leetcode 188

  public int maxProfit6(int k, int[] prices) {
    if(prices == null || prices.length ==0)
      return 0;
    if (k > prices.length/2) {
        k = prices.length/2;
    }
 
    int[][] dp = new int[prices.length][k+1];
    for (int j=0; j<=k; j++) {
      dp[0][j] = 0;
    }
    for (int i=0; i<prices.length; i++) {
      dp[i][0] = 0;
    }
 
    int max = 0;
    for(int i=1; i<prices.length; i++){
      for (int m = 0; m <=k; m++) {
 
        // dp[i][m] represents the max profit up until prices[i] using at most m transactions.
        // dp[i][m]  = max(dp[j][m-1] + diff, dp[i-1][m]) for 0=< j < i;
 
        dp[i][m] = dp[i-1][m];
        int v = 0;
        for (int j = 0; j < i; j++) {
          v = Math.max(v, m >= 1 ? dp[j][m-1] + prices[i] - prices[j] : 0);
        }
        dp[i][m] = Math.max(dp[i][m], v);
        max = Math.max(max, dp[i][m]);
      }
    }
 
    return max;
  }

local global strategy

stock leetcode 188

// 我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润,此为局部最优。
  // 然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润
  public int maxProfit3(int k, int[] prices) {
    if(prices == null || prices.length ==0)
      return 0;
    int[][] local = new int[prices.length][k+1];
    int[][] global = new int[prices.length][k+1];
    for (int i=0; i<prices.length; i++) {
      for (int j=0; j<=k; j++) {
        local[0][j] = 0;
        global[0][j] = 0;
      }
      local[i][0] = 0;
      global[i][0] = 0;
    }
 
    int max = 0;
    for(int i=1; i<prices.length; i++){
      for (int j = 1; j <=k; j++) {
        int diff = prices[i] - prices[i-1];
        // 其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值,和前一天的局部最优加上差值后相比
        // global -> local: j-1 -> j   // index change,
        // local  -> local: j   -> j   // index change,
 
        local[i][j] =  Math.max(global[i-1][j-1] + diff, local[i-1][j] + diff);
        // 全局最优比较局部最优和前一天的全局最优
        // local -> global  j   -> j // index = i
        // global -> global j   -> j // index change
        global[i][j] = Math.max(local[i][j], global[i-1][j]);
 
        // summary,
        // for local, index i always change from i- to i
        // for global j never change
      }
    }
 
    return global[prices.length-1][k];
  }

strategy for state upon prices[i]

trick for initialize.

stock leetcode 188

// hold[i][j]: For at most j transactions, the max profit on ith day with a stock in hand.
// unhold[i][j]: For at most j transactions, the max profit on ith day without a stock in hand

public int maxProfit22(int k, int[] prices) {
    if(k == 0 || prices.length < 2)
      return 0;
 
    int[][] hold = new int[prices.length][k+1];
    int[][] unhold = new int[prices.length][k+1];
 
    for(int j = 1; j <= k; j++) {
      hold[0][j] = - prices[0];  // with a stock at hand, the max profit is negative. notice trick here.
      unhold[0][j] = 0;
    }
    for(int i = 1; i < prices.length; i++) {
      for(int j = 1; j <= k; j++) {
        hold[i][j] = Math.max(-prices[i] + unhold[i-1][j-1], hold[i-1][j]); // Buy or not buy
        unhold[i][j] = Math.max(prices[i] + hold[i-1][j], unhold[i-1][j]); // Sell or not sell
      }
    }
    return unhold[prices.length-1][k];
  }

state machine strategy

used for states are co-related.

stock with cool down

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75928/Share-my-DP-solution-(By-State-Machine-Thinking)

wvR4TN8.png
public int maxProfit2(int[] prices) {
    if(prices == null || prices.length ==0)
      return 0;
    int[] s1 = new int[prices.length];
    int[] s2 = new int[prices.length];
    int[] s0 = new int[prices.length];
    s0[0]=0;
    s1[0]=prices[0]*-1;
    s2[0]=0;
    for(int i=1; i<prices.length; i++){
      s1[i] = Math.max(s1[i-1], s0[i-1]-prices[i]);
      s2[i] = s1[i]+prices[i];
      s0[i] = Math.max(s0[i-1], s2[i-1]);
    }
    return Math.max(s2[prices.length-1], s0[prices.length-1]);
  }

stock leetcode 188

public int maxProfit55(int k, int[] prices) {
    if(prices == null || prices.length ==0)
      return 0;
    int[][] s0 = new int[prices.length][k+1];
    int[][] s1 = new int[prices.length][k+1];
    for (int j=0; j<=k; j++) {
      if (j==0) {
        s1[0][j] = 0;
      } else if (j==1) {
        s1[0][j] = prices[0] * -1;
      } else {
        s1[0][j] = prices[0] * -1;  // impossible state using MIN_VALUE or return to self  by keeping the original value : prices[0] * -1;
      }
      s0[0][j] = 0;
    }
 
    for (int i=0; i<prices.length; i++) {
      s1[i][0] = 0;
      s0[i][0] = 0;
    }
 
    int max = 0;
    for(int i=1; i<prices.length; i++){
      for (int j = 1; j <=k; j++) {
        s0[i][j] = Collections.max(Arrays.asList(
            s1[i - 1][j] + prices[i], s0[i-1][j]));   // sell
 
        s1[i][j] = Collections.max(Arrays.asList(
            s1[i - 1][j], s0[i-1][j-1] - prices[i])); // buy
 
        max = Collections.max(Arrays.asList(max, s0[i][j]));
      }
    }
 
    return max;
  }

problem 1

Given a set {1,2,3,4,5,6,7,8,9,10}, write an algorithm that prints out all the n digits or lesser combinations that can arise out of the set.

condition: Successive numbers need to be avoided.

Eg; if set = {1,2,3,4,5,6,7,8,9,10}
and n = 3

It should print

(1,3,5) —> no successive numbers
(1,4,6)
(1,5,7}
(1,6,8}
(1,7,9}
{1,8,10}
(1,9)
(1,10)
.
.
(10, 1, 3)
(10, 2, 4)
so on so forth.

Here is the code.
Given: "1234" and N = 2
It would print out "13", "14", "24"
 
all other strings ("43","41"..) are just permutation of the above result.
Working code. Just copy and paste it to your favorite IDE then compile away.
 
#include <iostream>
#include <string>
void printComb(const char ar[], bool used[], int SIZE){
       string str = "";
       for (int i = 0; i < SIZE; ++i){
               if (used[i]){
                       str += ar[i];
               }
       }
       cout << str <<  endl;
}
 
//variable u keeps track of the number of
//characters in our result
 
void comb(const char ar[], bool used[], int index, int u, int N,  int SIZE){
       if (u == N){
               printComb(ar, used, SIZE);
       } else if (index >= SIZE){
               return;
       } else {
               used[index] = true;
               ++u;
               comb(ar, used, index + 2, u, N, SIZE);
               used[index] = false;
               --u;
               comb(ar, used, index + 1, u, N, SIZE);
       }
}
 
int main(){
       int N = 2;
       string str  = "1234";
       bool used[str.length()];
       for (int i = 0; i < str.length(); ++i){
               used[i] = false;
       }
       comb(str.c_str(), used, 0, 0, N, str.length());
}

problem 2 : subset of strings

Given a character array, print all the subsets of those characters

Ouput: x1…xn where xi denotes whether the i-th element of the input appears in the subset or not

#include <stdio.h>
#include <stdlib.h>
 
void gen(int* input, int n, int index);
 
int main(int argc, char* argv[])
{
   int *input;
   int n;
 
   if (argc != 2) {
        printf("Usage: %s <#elements>\n",argv[0]);
        exit(0);
   }
 
   n = atoi(argv[1]);
 
   input = malloc(sizeof(int)*n);
   gen(input,n,0);
}
 
void gen(int* input, int n, int index)
{
    int i;
 
    if (index == n) {
        for (i = 0; i < n; i++)
            printf("%d",input[i]);
        printf("\n");
       return;
    }
 
   input[index] = 0;
   gen(input,n,index+1);
   input[index] = 1;
   gen(input,n,index+1);
}

problems

http://people.csail.mit.edu/bdean/6.046/dp/
http://www.gabormelli.com/RKB/Algorithm_Strategy
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License