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

Graph Question - Hard Level - Question 1

2246. Longest Path With Different Adjacent Characters You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i. Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them. Constraints: n == parent.length == s.length 1 <= n <= 10^5 0 <= parent[i] <= n - 1 for all i >= 1 parent[0] == -1 parent represents a valid tree. s consists of only lowercase English letters. Analysis For this question, we need to construct a graph, or more specifically, a n-nary tree. How to construct the graph/tree? What we only know is the parent array. So we need to go through the parent array and constr...
Post a Comment
Read more