Dynamic Programming

Basic

Q : what is dynamic programming?
A : To solve a problem based on old knowledge.

Example - Fibonacci sequence
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …]
F(n) = F(n-1) + F(n-2)

It’s not easy to get F(100002) unless we have F(100001) and F(100000), so we consider using DP to figure out this problem since it is good at solving a problem based on old knowledge. First, we need something to store each state for future use, normally it can be an array dp[]. In Fibonacci, dp[i] is the i-th element of the sequence(i >= 1).

Q: How actually DP does when solving a problem?
A: Two patterns:

Bottom up
To get dp[n], we calculate array dp from dp[0] to dp[n].
Top down
To get dp[n] by recursion.

Bottom up

const getFibonacci_bottomUp = n => {
	let dp = [0, 1];
	if (n === 1 || n === 2) return dp[n - 1];
	for (let i = 3; i <= n; i++) {
		dp[i - 1] = dp[i - 2] + dp[i - 3];
	}
	return dp[n - 1];
}

Top down

const getFibonacci_topDown = n => {
	if (n === 1 || n === 2) return n - 1;
	return getFibonacci(n - 1) + getFibonacci(n - 2);
}

DP problems from leetcode

Palindrome

Q: What is a palindrome
A: A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar or the number 10201.

Q: How to check if it is a palindrome
A: See if it mirrors itself from it’s center.

#5 Longest Palindromic Substring
Solution:
Starting from the first character to the last of the target string, check how long it can expand from current character to both left and right sides to be a palindrome. Update the start and end position of the palindrome and return the substring.
My code

#132 Palindrome Partitioning II
Description:
Return the minimum cut(s) that can partition target s such that every substring is palindromic.
Example:
Input: “aab”
Output: 1
Explanation: The palindrome partitioning [“aa”,”b”] could be produced using 1 cut.
Solution:
In this problem, we just need to check if a substring is palindromic and then update the minimum cuts needed up to date . So we initialize an array dp[i] = i, it stores the maximum cost of cuts at i-th character, for example, s = "aaba", initialized dp = [0,1,2,3], dp[3] = 3 means at most 3 cuts to partition s at s.charAt(3), that is “a, a, b, a” (regard each comma as a cut). We update dp when a smaller cuts appeara.
My code

Unique Paths

#62 Unique Paths
Description:
Given m and n represent a m*n grid, find out how many ways there is from start(top left) to finish(down right).
Solution:
It’s quite like Fibonacci sequence, the number of ways to grid[i][j] is dp[i][j] = dp[i-1][j] + dp[i][j-1]. We scan row by row to calculate how many ways needed at each grid. And this 2-D array can be simplified to 1-D since we can update current row on previous one.
My code

#63 Unique Paths II
Description:
Given a 2-D array with 0 and 1 represents a mxn grid, grid with 1 means there is an obstacle. Find out how many ways there is from start(top left) to finish(down right).
Solution:
The only difference with #62 is that we need to check if grid[i][j] === 1 (has an obstacle), if so, we set dp[i] = 0.
My code

String

#32 Word Break
Description:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Solution:
We consider using DP, if the last segmented word is from Dict and previous words are, then running this string should return true. Boolean array DP[i] is used to store true or false whether s is satisfied at position i. A satisfied string’s DP[s.length] is true.
My code

Other

#32 Longest Valid Parentheses
Description:
Given a string containing ‘(‘ and ‘)’, find out the length of the longest well-formed parentheses substring. ‘()’ and ‘(())’ are consider valid.
Solution:
We consider using DP to solve this problem since the answer we need equals to 2( the last pair of ‘()’ when it exists) + valid longest length before the last pair.
We need an array DP[], DP[i] represents the longest length end at s.charAt(i), so DP[i] = 0 when s.charAt(i) = '(' which is not an end parenthese.
For s= "()()(())", DP = [0,2,0,4,0,0,2,8].
When s.charAt(i) = ')' we consider if one char before is ‘(‘
if so, DP[i] = 2 + DP[i-2] (when i >2)
if not, that is again a ‘)’ before current ‘)’, we check the char at the position way bcak to i-DP[i-1]-1, this means, for example s = "(()())", when i = 5, we check if char at 5 - DP[5-1] - 1 = 0 matches with s.charAt(5) to be a valid pair.
My code

#70 Climbing Stairs
Description:
Climbing n steps stairs, climb 1 or 2 steps at a time, how many climbing ways.
Solution:
Still like Fibonacci sequence( actually it is Fibonacci), the number of ways to stepi is ways(i) = ways(i-1) + ways(i-2), the basic case is 1 and 2 for stairs with one step and two steps. Either top down or bottom up works.
My code