Skip to main content

Dynamic Programming

The dynamic programming (dp) is one of the most intriguing realm in algorithm. The main purpose for dp is to avoid redundant calculations. One of the keys to achieve this is to solve the same problem with a smaller size. Once the same question with the smaller size is solved, the results can be stored and re-used directly when meet with the same problem again.

The populate word for dp is state, which means exactly the same question but different sizes (so the real idea behind dp is recursion, but with memoization). The state essentially is an abstract of the question to be solved. How to correctly define the state is one of two main difficulties for dp. 

The correct state means:

1. the state can fully describe the question to be solved;

2. the state transition formula can be derived based on the state definition.

The other difficulty is initialization. The initial states usually mean the question with very smaller sizes, so the results can be obtained without complex calculations. However, it turns out that the initialization depends on the  definition of the state, which is highly error-prone.

To sum up the key points for the dp:

1. how to define the state & state transition formula;

2. how to initialize the states which is the starting point of the dp.


 Example


Easy Level

Medium Level

Hard Level

Interview Questions


Upper Layer

Comments

Post a Comment

Popular posts from this blog

Brute Force - Question 2

2105. Watering Plants II Alice and Bob want to water n plants in their garden. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the ith plant is located at x = i. Each plant needs a specific amount of water. Alice and Bob have a watering can each, initially full. They water the plants in the following way: Alice waters the plants in order from left to right, starting from the 0th plant. Bob waters the plants in order from right to left, starting from the (n - 1)th plant. They begin watering the plants simultaneously. It takes the same amount of time to water each plant regardless of how much water it needs. Alice/Bob must water the plant if they have enough in their can to fully water it. Otherwise, they first refill their can (instantaneously) then water the plant. In case both Alice and Bob reach the same plant, the one with more water currently in his/her watering can should water this plant. If they have the same amount of water, then Alice ...
Post a Comment
Read more

Sweep Line

Sweep (or scanning) line algorithm is very efficient for some specific questions involving discrete intervals. The intervals could be the lasting time of events, or the width of a building or an abstract square, etc. In the scanning line algorithm, we usually need to distinguish the start and the end of an interval. After the labeling of the starts and ends, we can sort them together based on the values of the starts and ends. Thus, if there are N intervals in total, we will have 2*N data points (since each interval will contribute 2). The sorting becomes the most time-consuming step, which is O(2N*log(2N) ~ O(N*logN). After the sorting, we usually can run a linear sweep for all the data points. If the data point is labeled as a starting point, it means a new interval is in the processing; when an ending time is reached, it means one of the interval has ended. In such direct way, we can easily figure out how many intervals are in the processes. Other related information can also be obt...
Post a Comment
Read more

Graph - Medium Level - Question 1

Graph - Medium Level - Question 1 Leetcode 2049. Count Nodes With the Highest Score There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n - 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1. Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees. Return the number of nodes that have the highest score. Constraints: n == parents.length 2 <= n <= 10^5 parents[0] == -1 0 <= parents[i] <= n - 1 for i != 0 parents represents a valid binary tree. Analysis: If we have had the binary tree, then we just can do a top-down count, to count the number of nodes for the sub-tree with the root as the curren...
Post a Comment
Read more