Dynamic Programming - State Machine

Best Time to Buy and Sell Stocks

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.

One Transaction (record min price and max profit)

Problem link

One Transaction

One Transaction

1
2
3
4
hold[i] = max(hold[i-1], -price[i]);              // hold[0] = -price[0]
sell[i] = max(sell[i-1], hold[i-1]+price[i]); // sell[0] = INT_MIN

result = sell[n];

Multiple Transaction

Problem link

Multiple Transaction

Multiple Transaction

1
2
3
4
hold[i] = max(hold[i-1], sell[i-1]-price[i]);       // hold[0] = -price[0]
sell[i] = max(sell[i-1], hold[i-1]+price[i]); // sell[0] = 0

result = sell[n];

Multiple Transaction with Transaction Fee

Problem Link

Multiple Transaction with Transaction Fee

Multiple Transaction with Transaction Fee

1
2
3
4
hold[i] = max(hold[i-1], sell[i-1]-prices[i]);
sell[i] = max(sell[i-1], hold[i-1]+prices[i]-fee);

result = sell[n];

Multiple Transaction with Cooldown

Problem Link

Multiple Transaction with Cooldown

Multiple Transaction with Cooldown

1
2
3
4
5
rest[i] = max(sell[i-1], rest[i-1]);          // rest[0] = 0
hold[i] = max(rest[i-1]-price[i], hold[i-1]); // hold[0] = -price[0]
sell[i] = hold[i-1]+price[i]; // sell[0] = INT_MIN

result = max(sell[n], rest[n])

At most Two Transactions

Problem link

At most two transactions

At most two transactions

1
2
3
4
5
6
hold[0][i] = max(hold[0][i-1], -price[i]);
sell[0][i] = max(sell[0][i-1], hold[0][i]+price[i]);
hold[1][i] = max(hold[1][i-1], sell[0][i]-price[i]);
sell[1][i] = max(sell[1][i-1], hold[1][i]+price[i]);

result = max(sell[0][n], sell[1][n]);

At most k Transactions

Problem Link

At most K transactions

At most K transactions

1
2
3
4
5
6
7
8
9
10
11
12
for (int j = 0; j < k+1; j++) {
sell[j] = 0;
hold[j] = INT_MIN;
}
for (int i = 0; i < n; i++) {
for (int j = k; j > 0; j--) { // bottom up update
sell[j] = max(sell[j], hold[j] +price[i]);
hold[j] = max(hold[j], sell[j-1]-price[i]);
}
}

result = sell[k];

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Array Neighbourhood

House Robber

House Robber

1
2
3
4
// broken[i]  max amount if house i has been broken into
// passed[i] max amount if house i is safe
broken[i] = passed[i-1] + nums[i] ; // broken[0] = nums[0];
passed[i] = max(broken[i-1], passed[i-1]); // passed[0] = 0;

Circle Neighbourhood

Problem can simply be decomposed into two House Robber problems: since house 0 and n-1 are now neighbors, at least one of house 0 and n-1 must be safe in one night, which is equivalent to the maximum of

  • rob(1, n-1)
  • rob(0, n-2)

Binary Tree Neighbourhood

There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

1
2
3
4
5
6
int r1 = root->val
+ (root->left ? rob(root->left->left) + rob(root->left->right) : 0)
+ (root->right ? rob(root->right->left) + rob(root->right->right) : 0);
int r2 = rob(root->left) + rob(root->right);

return std::max(r1, r2);

Paint House

Min Cost 3 Colors

For n houses, each house can be painted with one of the three colors (0, 1, 2). No two adjacent houses have the same color. The cost of painting each house with a certain color is represented in a n*3 matrix costs.

Paint House

Paint House

1
2
3
// cost[i][j]: total cost till the ith house with color j
for (int j = 0; j < 3; j++)
cost[i][j] = min(cost[i-1][(j+1)%3 ], cost[i-1][(j+2)%3]) + costs[i][j];

Min Cost for K Colors

1
2
3
4
5
6
7
8
for (int j = 0; j < K; j++){
int last = INT_MAX;
for (int k = 1; k < K; t++) {
if (cost[i-1][(j+k)%K] < last)
last = cost[i-1][(j+k)%K];
}
cost[i][j] = last + costs[i][j];
}

Number of Paint Ways for K Colors

1
2
3
4
5
6
for (int i = 2; i < n; i++) {
same[i] = diff[i-1]; // same[1] = k;
diff[i] = (same[i-1] + diff[i-1]) * (k-1); // diff[1] = k * (k-1);
}

return diff[n-1] + same[n-1];

Meeting Room II

Problem link

Sort events based on time.

1
2
3
4
5
6
7
8
vector<int> start, end;
for (auto itv : intervals) {
start.push_back(itv[0]);
end.push_back(itv[1]);
}

sort(start.begin(), start.end());
sort(end.begin(), end.end());

Event driven state machine. If there’s a tie, perform end event first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int num_room_total = 0;
int num_room_avail = 0;
int idx_start = 0, idx_end = 0;
while (idx_start < intervals.size()) {
if (start[idx_start] < end[idx_end]) {
if (num_room_avail == 0) {
num_room_total ++;
} else {
num_room_avail --;
}
idx_start++;
} else {
num_room_avail ++;
idx_end++;
}
}

return num_room_total;

Meeting Room II

Meeting Room II

Regular Expression Matching