动态规划(Dynamic Programming)
3. Longest Substring Without Repeating Characters
题目链接 https://leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Solution：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
};
5. Longest Palindromic Substring
题目链接 https://leetcode.com/problems/longest-palindromic-substring/
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
解法一：暴力求解:
解法二： 动态规划:
简单来说就是从左到右，两层循环，判断两层循环间形成的区间能否形成回文串。时间复杂度为O(N)
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
int start = 0, max_len = 1;
bool dp[n][n];
for(int i = 0; i < n; ++i)
for(int j = 0; j <= i; ++j){
if(i - j <= 1)
dp[j][i] = s[j]==s[i];
else{
dp[j][i] = (s[j]==s[i]) && dp[j+1][i-1];
}
if(dp[j][i] && max_len < i-j+1){
start = j;
max_len = i - j + 1;
}
}
return s.substr(start, max_len);
}
};
516. Longest Palindromic Subsequence
题目链接 https://leetcode.com/problems/longest-palindromic-subsequence/
Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "bbbab"
Output: 4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input: "cbbd"
Output: 2
One possible longest palindromic subsequence is "bb".
思路:
对于任意字符串，如果头尾字符相同，那么字符串的最长子序列等于去掉首尾的字符串的最长子序列加上首尾；如果首尾字符不同，则最长子序列等于去掉头的字符串的最长子序列和去掉尾的字符串的最长子序列的较大者。
设字符串为s，dp[i][j]表示第i到第j个字符间的最长回文子序列的长度（i<=j），则转态转移方程为：
\[dp[i][j] = \begin{cases} dp[i+1][j-1] + 2 &if(s[i] == s[j]) \\ max(dp[i+1][j], dp[i][j-1]) &if(s[i] != s[j])\end{cases}\]DP解法:
class Solution {
public:
int longestPalindromeSubseq(string s) {
int len = s.size();
vector< vector<int> > dp(len, vector<int>(len));
for(int i = len - 1; i >= 0; i--){
dp[i][i] = 1;
for(int j = i + 1; j < len; j++){
if(s[i] == s[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][len-1];
}
};
542. 01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
[[0,0,0],
[0,1,0],
[0,0,0]]
Output:
[[0,0,0],
[0,1,0],
[0,0,0]]
Example 2:
Input:
[[0,0,0],
[0,1,0],
[1,1,1]]
Output:
[[0,0,0],
[0,1,0],
[1,2,1]]
动态规划解法:
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int row = matrix.size(), col = matrix[0].size();
vector<vector<int>> dist(row, vector<int>(col, INT_MAX));
int max_dist = row * col;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(matrix[i][j] == 0)
dist[i][j] = 0;
else{
int upcell = (i > 0) ? dist[i-1][j] : max_dist;
int leftcell = (j > 0) ? dist[i][j-1] : max_dist;
dist[i][j] = min(upcell, leftcell) + 1;
}
}
}
for(int i = row - 1; i >= 0; i--){
for(int j = col - 1; j >= 0; j--){
if(matrix[i][j] == 0)
dist[i][j] = 0;
else{
int downcell = (i < row - 1) ? dist[i+1][j] : max_dist;
int rightcell = (j < col - 1) ? dist[i][j+1] : max_dist;
dist[i][j] = min(min(downcell, rightcell) + 1, dist[i][j]);
}
}
}
return dist;
}
};
96. Unique Binary Search Trees
题目链接 https://leetcode.com/problems/unique-binary-search-trees/
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
动态规划解法:
class Solution {
public:
int numTrees(int n) {
int *G = new int[n+1]();
G[0] = 1; G[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
G[i] += G[j-1] * G[i-j];
}
}
return G[n];
}
};
解答思路:
问题的描述是：给定1~n的数字，将其存储到一棵二叉搜索树上，共有多少种不同的结构？
给定一个序列1 ~ n，要构造BST，我们可以这么思考。根据BST的性质，某个节点的所有左子树的值都比该节点小，右子树的值都比该节点大。因此，当选择序列中的某个值(例如就叫m)作为根节点时，显然其左边的数值1 ~ m-1都会在它的左子树上，而其右边的值m+1 ~ n都会在其右子树上。也就是说，它的左子树将由1 ~ m-1构成一棵BST，其右子树将由m+1 ~ n构成另外一棵BST。这显然是一个清晰的动态规划的最优子结构。
下面定义几个函数：
G(N):序列长度为N时，结构不同的BST的个数
F(i, N), 1 <= i <= N: 序列长度为N，以i为根节点时BST的个数
我们需要计算的是G(N)，而显然有
G(N) = F(1, N) + F(2, N) + ... + F(N, N)。
初始值为G(0) = 1, G(1) = 1。
下一个问题是如何计算F(i, N)。上面说了，F(i, N)表示序列长度为N，以i为根节点时BST的个数。那么显然，左边的子树由1 ~ i-1构成，它共有G(i-1)种不同的构成方式；右边的子树由i+1 ~ N构成，他们是依次递增的序列，和1 ~ N-i的序列构成的子树是一样的效果，因此也有G(N-i)种不同的服务。因此我们有
F(i, N) = G(i - 1) * G(N - i) 1 <= i <= N
结合G(N)的计算公式，我们可以得到
G(N) = G(0) * G(N - 1) + G(1) * G(N - 2) + ... + G(N - 1) * G(0)
于是代码也就一目了然了:
public int numTrees(int n) {
int [] G = new int[n+1];
G[0] = G[1] = 1;
for(int i=2; i<=n; ++i) {
for(int j=1; j<=i; ++j) {
G[i] += G[j-1] * G[i-j];
}
}
return G[n];
}
95. Unique Binary Search Trees II
题目链接 https://leetcode.com/problems/unique-binary-search-trees-ii/
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
动态规划解法:
class Solution {
private:
vector<TreeNode*> helper(int start, int end){
vector<TreeNode*> res;
if(start > end) {
res.push_back(NULL);
return res;
}
for(int i = start; i <= end; i++){
vector<TreeNode*> lefts = helper(start, i - 1);
vector<TreeNode*> rights = helper(i + 1, end);
for(int j = 0; j < (int)lefts.size(); j++){
for(int k = 0; k < (int)rights.size(); k++){
TreeNode* root = new TreeNode(i);
root->left = lefts[j];
root->right = rights[k];
res.push_back(root);
}
}
}
return res;
}
public:
vector<TreeNode*> generateTrees(int n) {
if(n == 0) return vector<TreeNode*>(0);
return helper(1,n);
}
};
338. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
解题思路:
举例说明，例如当num=14时，其二进制编码为1110，显然共有3个1。此时我们发现num-1=13，而13的二进制编码为1101，两者做异或之后为1100，共有2个1，于是得出动态规划的推导公式：
dp[i] = dp[i&(i-1)] + 1
动态规划解法:
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ret(num+1, 0);
for(int i = 1; i <= num; i++){
ret[i] = ret[i&(i-1)] + 1;
}
return ret;
}
};
931. Minimum Falling Path Sum
题目链接 https://leetcode.com/problems/minimum-falling-path-sum/
Given a square array of integers A, we want the minimum sum of a falling path through A.
A falling path starts at any element in the first row, and chooses one element from each row. The next row’s choice must be in a column that is different from the previous row’s column by at most one.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation:
The possible falling paths are:
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9][2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9][3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]- The falling path with the smallest sum is [1,4,7], so the answer is 12.
思路:
简单来说，就是
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
动态规划解法:
int minFallingPathSum(vector<vector<int>>& A) {
for (auto i = 1; i < A.size(); ++i)
for (auto j = 0; j < A.size(); ++j)
A[i][j] += min({ A[i-1][j], A[i-1][max(0,j-1)], A[i-1][min((int)A.size()-1,j+1)] });
return *min_element(begin(A[A.size() - 1]), end(A[A.size() - 1]));
}
1143. Longest Common Subsequence
题目链接 https://leetcode.com/problems/longest-common-subsequence/
Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
动态规划解法:
class Solution {
public:
int longestCommonSubsequence(string s, string t) {
int m = s.length(), n = t.length();
if(m == 0 || n == 0) return 0;
int **ret = new int*[m];
for(int i = 0; i < m; i++){
ret[i] = new int[n];
}
// 初始化第一行和第一列
ret[0][0] = (s[0] == t[0]) ? 1 : 0;
for(int i = 1; i < n; i++)
ret[0][i] = ret[0][i-1] + (s[0] == t[i]) ? 1 : 0;
for(int i = 1; i < m; i++)
ret[i][0] = ret[i-1][0] + (s[i] == t[0]) ? 1 : 0;
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
ret[i][j] = max(ret[i-1][j], ret[i][j-1]);
if(s[i] == t[j]) ret[i][j] = ret[i-1][j-1] + 1;
}
}
return ret[m-1][n-1];
}
};
1027. Longest Arithmetic Sequence
题目链接 https://leetcode.com/problems/longest-arithmetic-sequence/
Given an array A of integers, return the length of the longest arithmetic subsequence in A.
Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
Note:
2 <= A.length <= 20000 <= A[i] <= 10000
思路:
最优子结构为dp[i][diff] = dp[j][diff] + 1
动态规划解法:
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
int n = A.size(), ret = 2;
vector<unordered_map<int, int>> dp(n, unordered_map<int, int>());
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
int diff = A[i] - A[j];
if(dp[j].find(diff) == dp[j].end())
dp[i][diff] = 2;
else{
dp[i][diff] = dp[j][diff] + 1;
ret = max(ret, dp[i][diff]);
}
}
}
return ret;
}
};
300. Longest Increasing Subsequence
题目链接 https://leetcode.com/problems/longest-increasing-subsequence/
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in $O(n^2)$ complexity.
Follow up: Could you improve it to $O(n \log n)$ time complexity?
动态规划解法一($O(n^2)$):
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
if(len <= 1) return len;
int *dp = new int[len];
for(int i = 0; i < len; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
}
int res = 0;
for(int i = 0; i < len; i++)
if(dp[i] > res)
res = dp[i];
return res;
}
};
动态规划解法二 ($O(n \log n)$):
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(auto val: nums){
auto it = lower_bound(res.begin(), res.end(), val);
if(it == res.end()) res.push_back(val);
else *it = val;
}
return res.size();
}
};
1227. Airplane Seat Assignment Probability
题目链接 https://leetcode.com/problems/airplane-seat-assignment-probability/
n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of passengers will:
- Take their own seat if it is still available,
- Pick other seats randomly when they find their seat occupied
What is the probability that the n-th person can get his own seat?
Example 1:
Input: n = 1
Output: 1.00000
Explanation: The first person can only get the first seat.
Example 2:
Input: n = 2
Output: 0.50000
Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).
Solution:
设f(n)为第n个人坐到自己座位的概率，有两种情况可以达成这一目标：
- 第一个人恰巧坐到了第一个座位，于是后面的所有人都坐到了自己的座位，这一情况发生的概率
P_1 = 1/n - 第一个人随机地坐到了第2到
n-1的座位上，于是下面要分情况讨论——
如果第一个人随机地坐到了第2个座位上，那么第2个人不幸地就成为了那个不幸的人，那么他可以选择的座位有1，3，4，5...n一共n-1个，于是化归为子问题f(n-1)
如果第一个人随机地坐到了第3个座位上，那么第2个人可以坐自己的座位，第3个人成为了不幸的人，他可以选择的座位有1，4，5...n一共n-2个，于是化归为子问题f(n-2)
......
以此类推
第二种情况发生的概率为： \(\begin{aligned} P_2 &= \frac{n-2}{n} * [\frac{1}{n-2}*f(n-1) + \frac{1}{n-2}*f(n-2)+\dots+\frac{1}{n-2}*f(1)] \\ &=\frac{1}{n}*[f(n-1) + f(n-2) + \dots + f(2)] \end{aligned}\)
详细解释为：
(n-2) / n -----> 第一个人坐到了2~(n-1)的座位上
(1/(n-2) * f(n-1) -----> 第一个人坐到了第2个座位上
+ 1/(n-2) * f(n-2) -----> 第一个人坐到了第3个座位上
+ ......
+ 1/(n-2) * f(2) -----> 第一个人坐到了第n-1个座位上
于是第n个人坐在自己的座位上的概率为
\[\begin{aligned} f(n) &= \frac{1}{n} + \frac{1}{n}*[f(n-1) + f(n-2) + \dots + f(2)] \\ &= \frac{1}{n}*[f(n-1) + f(n-2) + \dots + f(1)] \\ \end{aligned}\]同时有：
\[f(n-1) = \frac{1}{n-1}*[f(n-2) + f(n-3) + \dots + f(1)]\]两边同乘，得到
\[\begin{aligned} n * f(n) &= f(n-1) + f(n-2) + \dots + f(1) \\ (n-1) * f(n-1) &= f(n-2) + \dots + f(1) \end{aligned}\]上下相减得到
\[n * f(n) - (n-1) * f(n-1) = f(n-1)\]移项后有
\[n * f(n) = n * f(n-1),n \ge 2\]于是有
f(1) = 1, f(2) = f(3) = ... = f(n) = 1/2
代码如下:
class Solution {
public:
double nthPersonGetsNthSeat(int n) {
return n == 1 ? 1.0 : 0.5;
}
};
413. Arithmetic Slices
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
思路:
题目要求寻找A[i]中等差数列的数目，设dp[i]为以A[i]结尾的序列的等差序列的数目，显然有dp[0] = dp[1] = 0。由于等差数列具有传递性，如果A[i-3],A[i-2],A[i-1]能构成等差数列，同时A[i-2],A[i-1],A[i]也能构成等差数列，那么A[i-3],A[i-2],A[i-1],A[i]显然也能构成等差数列。所以最终DP的公式为
以A=[1,2,3,4,5]为例，dp[0]=dp[1]=0，dp[2]=1（[1,2,3]可以构成等差数列），dp[3]=dp[2]+1=2（因为A[3] - A[2] == A[2] - A[1]）…….
最后得到的dp数组是：
A: 1 2 3 4 5
dp: 0 0 1 2 3
而题目要求寻找A[i]中等差数列的数目，等差数列可以以任意位置结尾（只要长度大于等于3），因为直接将dp数组求和即可，结果为6
Solution：
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int cur = 0, res = 0;
for(int i = 2; i < A.size(); i++){
if(A[i] - A[i-1] == A[i-1] - A[i-2]){
cur += 1;
res += cur;
} else {
cur = 0;
}
}
return res;
}
};
1048. Longest String Chain
Given a list of words, each word consists of English lowercase letters.
Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".
A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.
Example 1:
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".
思路:
- 与最长递增子序列方法相同，自底而上的完成
- 可以自顶而下，每次删除字符串完成
dp[word] = max(dp[word], dp[word - ch] + 1)
其中，word - ch表示字符串word删除其任何一个字符得到的新字符串
Solution:
class Solution {
public:
int longestStrChain(vector<string>& words) {
if(words.size() < 2) return words.size();
int max_len = 1;
map<string, int> m;
for(string word: words){
m[word] = 1;
}
sort(words.begin(), words.end(), [](string& a, string& b){return a.size() < b.size();});
for(string w: words){
int len = w.size();
if(len != 1){
for(int i = 0; i < len; i++){
string new_str = "";
if(i == 0)
new_str = w.substr(1, len - 1);
else
new_str = w.substr(0, i) + w.substr(i+1, len-i-1);
if(m.find(new_str) != m.end())
m[w] = max(m[w], m[new_str] + 1);
}
}
if(m[w] > max_len) max_len = m[w];
}
return max_len;
}
};
1277. Count Square Submatrices with All Ones
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
Explanation:
dp[i][j] means the size of biggest square with A[i][j] as bottom-right corner.
dp[i][j] also means the number of squares with A[i][j] as bottom-right corner.
If A[i][j] == 0, no possible square.
If A[i][j] == 1,
we compare the size of square dp[i-1][j-1], dp[i-1][j] and dp[i][j-1].
min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 is the maximum size of square that we can find.
Solution:
class Solution {
public:
int countSquares(vector<vector<int>>& A) {
int res = 0;
for (int i = 0; i < A.size(); i++)
for(int j = 0; j < A[0].size(); res += A[i][j++])
if(A[i][j] && i && j)
A[i][j] += min({A[i-1][j], A[i][j-1], A[i-1][j-1]});
return res;
}
};
