# Dynamic Programming - State Machine

# Best Time to Buy and Sell Stocks

Say you have an array for which the `i`

th 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)

1 | hold[i] = max(hold[i-1], -price[i]); // hold[0] = -price[0] |

#### Multiple Transaction

1 | hold[i] = max(hold[i-1], sell[i-1]-price[i]); // hold[0] = -price[0] |

#### Multiple Transaction with Transaction Fee

1 | hold[i] = max(hold[i-1], sell[i-1]-prices[i]); |

#### Multiple Transaction with Cooldown

1 | rest[i] = max(sell[i-1], rest[i-1]); // rest[0] = 0 |

#### At most Two Transactions

1 | hold[0][i] = max(hold[0][i-1], -price[i]); |

#### At most *k* Transactions

1 | for (int j = 0; j < k+1; j++) { |

# 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

1 | // broken[i] max amount if house i has been broken into |

#### 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 | int r1 = root->val |

# 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`

.

1 | // cost[i][j]: total cost till the ith house with color j |

#### Min Cost for K Colors

1 | for (int j = 0; j < K; j++){ |

#### Number of Paint Ways for K Colors

1 | for (int i = 2; i < n; i++) { |

#### Meeting Room II

Sort events based on time.

1 | vector<int> start, end; |

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

1 | int num_room_total = 0; |