相同：都能分解为若干个子问题
不同：DP存储子问题的结果
动态规划介绍- Build approach from sub-problems to the final destination
- Recursion的空间与时间成本
- Bottom-Up与Top-Down
Fibonacci Number
1, 1, 2, 3, 5… NON-Dynamic Programming
1 ⾃顶向下
int Fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
2 ⾃底向上
int array[n] = {0};
array[1] = 1;
for (int i = 2; i < n; i++)
array[i] = array[i-1] + array[i-2];
动态规划的4个要点1、状态（存储小规模问题的结果）
2、方程（状态之间的联系，怎么通过小的状态，来算大的状态）
3、初始化（最极限的小状态是什么）
4、答案（最大的那个状态是什么）
1 ⽤Dynamic Programming (Bottom-Up) 解决收敛结构问题可以把上述递推关系写在⼿边，这样做⾮常有利于理清算法实现的思路。
例如对于斐波那契数列，有递推式：
f(n) = G[f(n-1), f(n-2)] = f(n-1) + f(n-2)
如果出现类似于**“所有解”，“所有路径”**等关键词，则⽤Top-down⽅法更为直接。
Prime
生成第n个质数
int GetNthPrime(int n) {
list primers(1, 2);
int number = 3;
while (primers.size()!=n) {
bool isPrime = true;
for (auto it = primers.begin(); it != primers.end() && (*it) * (*it) <= number; it++) {
if (number % (*it) == 0) {
isPrime = false; break;
}
}
if (isPrime)primers.push_back(number);
number += 2;
}
return *(primers.rbegin());
}
Word Break
给定一个字符串s和一个字典dict，判断字符串能否有字典中的字符串组成，字典中的字符串可以出现多次。
例如s=“Ilovebytedance”,dict={“I”,“love”,“bytedance”}
//dp[n+1]存储第b个字符是否符合要求 bool wordBreak(string s, unordered_set& dict) { int begin = 0, end = 0; int n = s.size(); vector dp(n+2,false); dp[0] = true; for (end = 0; end <= n; end++) { for (begin = 0; begin <= end; begin++) { if (dp[begin] && (dict.find(s.substr(begin, end - begin + 1)) != dict.end())) { dp[end + 1] = true; break; } } } return dp[n]; }
Palindrome Partition
回文最小分割数
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的 最少分割次数 。
本题可以分为两个部分：判断字串是不是回⽂(palindrome)，如何切割原字符串。
isPalindrome( i , j ) = (value(i) == value(j)) AND ( isPalindrome(i+1, j-1) OR j – i <= 1 ) ， i和j分别表⽰substring的⾸坐标和尾坐标
minCut(i) = min(minCut(j+1)+1)，for i <= j < n, and substring(i , j) is palindrome。
int mincut(string s) {
if (s.empty())return 0;
vector> palin(s.size(), vector(s.size(), false));
vector minCut(s.size()+1, 0);
for (int i = 0; i <= s.size(); i++)minCut[i] = s.size() - i - 1;
for (int i = s.size(); i >=0 ; i--)
for (int j = i; j
“聚合”性质
求最值或者求和问题，往往可以进⼀步优化DP Table的空间。如果只在乎紧邻的前⼀个的局部解，⽽不在乎前⼏个局部解的问题，就可以接受每次在计算当前解的时候，替换掉那个最优解。
Unique Path II
Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. There is one obstacle in the middle of a 3x3 grid as illustrated below.
[[0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is 2
当(i, j)有障碍时dp[i][j] = 0
dp[0][j]和dp[i][0]未必为1.
dp[0][j] = obstacleGrid[0][j] ? 0 : dp[0][j-1]
dp[i][0] = obstacleGrid[i][0] ? 0 : dp[i-1][0]
当obstacleGrid [0][0] = 1时，return 0
Triangle
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0h5gP7qX-1660054528891)(C:Users13415AppDataRoamingTyporatypora-user-imagesimage-20220801233158315.png)]
要求空间复杂度在O(n)
//最后一个使用完父节点之后在进行替换，所以采用逆序
int mininumTotal(vector>& triangle) {
//行号既是行号，也是该行的元素个数(金字塔特性),也是该行的最后一个元素的index
int row = triangle.size();
if (row == 0)
return 0;
vector total(row, 1000000);
total[0] = triangle[0][0];
for (int i = 1; i < row; i++) {
for (int j = i; j >= 0; j--) {//
if (j == 0) {
total[j] = total[j] + triangle[i][j];
}
else {
total[j] = min(total[j - 1] ,total[j]) + triangle[i][j];
}
}
}
int min_=10100000;
for (int i = 0; i < row;i++) {
min_ = min(min_, total[i]);
}
return min_;
}
Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example, Given n = 3, there are a total of 5 unique BST’s.
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TmUtFJ9w-1660054528893)(C:Users13415AppDataRoamingTyporatypora-user-imagesimage-20220801234604918.png)]
int numTrees(int n) {
vector dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for(int k=0;k
最⻓⼦序列的问题
对于“最长⼦序列”问题(即有限空间内，满⾜⼀定条件的最长顺序⼦序列)，本⾝具有很强的聚合性，可以以如下⽅式解答：⽤DP Table来记录以当前节点为末节点的序列的解(⾄少固定问题的⼀端，因此不是以“当前节点或之前节点”为末节点)的解，并根据递推关系，由问题空间的起点到达问题空间的终点。
Longest Sub Sequence
Find the longest increasing subsequence in an integer array. E.g, for array {1, 3, 2, 4}, return 3.
maxLength(i) = max{ maxLength(k), k = 0~i-1 and array[i] > array[k] } + 1;
int LongestIncreasingSubsequence(vector s, int n) {
vector dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if(s[i]>s[j])
dp[i] = max(dp[i], dp[j] + 1);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, dp[i]);
}
return ans;
}
Gas Station
Suppose you are traveling along a circular route. On that route, we have N gas stations for you, where the amount of gas at station i is gas[i]. Suppose the size of the gas tank on your car is unlimited. To travel from station i to its next neighbor will cost you cost[i] of gas. Initially, your car has an empty tank, but you can begin your travel at any of the gas stations. Please return the smallest starting gas station’s index if you can travel around the circuit once, otherwise return -1.array[i] = gas[i] – cost[i]。
问题转化为，找到⼀个起始位置index，将array依此向左shift，即index->0(index对应新的数组下标0)，index+1->1…，使得对于任意0 <= i < n，满⾜序列和subSum(0, i)⼤于0。
int canCompleteCircuit(vectorgas, vectorcost) {
int sum;
vector arr;
for (int i = 0; i < gas.size(); i++) {
arr.push_back( gas[i] - cost[i]);
sum += gas[i] - cost[i];
}
if (sum < 0) {
return -1;
}
int index=0;
int subsum = 0;
for (int i = 0; i < arr.size(); i++) {
subsum += arr[i];
if (subsum < 0) {
index = i + 1;//前面的点为出发点不行，后面的点可以，当前这个点也可以（满足subsum>=0条件的当前点一定可以到达后面的点）
subsum = 0;
}
}
return index;
}
Longest Common Sequence
Please write a function to calculate the Longest Common Subsequence (LCS) given two strings.
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.
Length(i,j) = (str1[i-1] == str2[j-1]) ? Length(i-1, j-1) + 1 ： Max { Length(i,j-1), Length(i-1,j) }
int lcs(string str1,string str2) {
vector> length(str1.size() + 1, vector(str2.size() + 1));
for (int i = 0; i <= str1.size(); i++) {
for (int j = 0; j <= str2.size(); j++) {
if (i == 0 || j == 0)
length[i][j] = 0;
else if (str1[i - 1] == str2[j - 1])
length[i][j] = length[i - 1][j - 1] + 1;
else
length[i][j] = max(length[i-1][j],length[i][j-1]);
}
}
return length[str1.size()][str2.size()];
}
2 模式识别
如果当前节点的解，既依赖于前驱问题的解，又依赖于后驱问题的解，但这两部分又互相独⽴，则可以分别⾃左开始DP，计算从最左节点到当前节点的结果；⾃右开始DP，计算从最右节点到当前节点的结果；再⽤同⼀个DP Table来合并解。
Product without self
Given an array of integers, write a function to replace each element with the product of all elements other than that element.
假定数组A={4, 3, 2, 1, 2}，则OUTPUT={12, 16, 24, 48, 24}。
先求从左到右的求和，再求从右到左的求和。（其他方法比如求全体和，再做除法，存在着除0报错、大整数越界的可能性）
void replaceWithProducts_(vector vec) {
int n = vec.size();
int p = 1;
int dp_left[10000], dp_right[1000];
for (int i = 0; i < n; i++) {
dp_left[i] = p;
p *= vec[i];
}
p = 1;
for (int i = n - 1; i >= 0; i--) {
dp_right[i] = p;
p *= vec[i];
}
int ans[1000];
for (int i = 0; i < n; i++) {
ans[i] = dp_left[i] * dp_right[i];
cout << ans[i] << " ";
}
cout << endl;
}
void replaceWithProducts(vector vec) {
int n = vec.size();
int p = 1;
int dp_left[10000], dp_right[1000];
for (int i = 0; i < n; i++) {
dp_left[i] = p;
p *= vec[i];
}
p = 1;
for (int i = n - 1; i >= 0; i--) {
dp_right[i] = p*dp_left[i];
p *= vec[i];
}
for(int i=0;i
Hold Water
You are given an array of n non-negative integers. Each value means the height of a histogram. Suppose you are pouring water onto them, what is the maximum water it can hold between a left bar and a right bar (no separation)?
当前节点的储⽔量，等于左侧最⾼海拔与右侧最⾼海拔的较⼩值减去当前节点的海拔。
int trap(int A[], int n) {
if (n <= 0) return 0;
vector dp(n, 0);
int left_max = 0;
for (int i = 0; i < n; i++) {
dp[i] = left_max;
if (A[i] > left_max)
left_max = A[i];
}
int right_max=0,water=0;
for (int i = n - 1; i >= 0; i--) {
if (min(dp[i], right_max) > A[i])
water += min(dp[i], right_max) - A[i];
if (A[i] > right_max)
right_max = A[i];
}
return water;
}
3 ⽤Memorization Technique(Top-Down)解决收敛结构问题
Memorization是Top-Down形式的Dynamic Programming，也可以⽤来解决前述的问题(但空间上可能效率不及Bottom-Up形式的DP)。
Memoization的核⼼在于，在原有递归框架下，储存⼦问题的计算结果，在重复计算⼦问题时返回已经计算的。
Tallest stack of boxes
Given a set of boxes, each one has a square bottom and height of 1. Please write a function to return the tallest stack of these boxes. The constraint is that a box can be put on top only when its square bottom is restrictively smaller.
class Box {
public:
int bottom_size;
Box(int a) {
bottom_size = a;
}
Box() = default;
bool operator==(const Box& b) const
{
return bottom_size == b.bottom_size;
}
bool canBeAbove(Box bottom) {
if (this->bottom_size < bottom.bottom_size)
return true;
return false;
}
};
struct hash_name {
size_t operator()(const Box& p) const {
return hash()(p.bottom_size);
}
};
//返回以bottom为最低点时，堆叠的最高方式
vector createStackDP(Box boxes[],const int num,Box bottom,unordered_map,hash_name> stackCache) {
//memorization
if (stackCache.count(bottom) > 0)
return stackCache[bottom];
//以bottom为底时，在全部点中找到可以放的box,保存可以叠最高的那个box
vector new_stack;
vector max_stack;
size_t max_height = 0;
for (int i = 0; i < num; i++) {
if (boxes[i].canBeAbove(bottom))
new_stack = createStackDP(boxes, num, boxes[i], stackCache);
if (new_stack.size() > max_height) {
max_height = new_stack.size();
max_stack = new_stack;
}
}
max_stack.insert(max_stack.begin(), bottom);
stackCache[bottom] = max_stack;
return max_stack;
}
Word Break II
Given a string and a dictionary of words, please write a function to add space into the string, such that the string can be completely segmented into several words, where every word appears in the given dictionary.
//topdown,考虑用memorization的理由是，当前节点以后的拆分方法是否满足条件，与当前节点的拆分方法无关，
//子串的拆分重复计算，把substr作为memorization的key，拆分结果的集合作为value
vector wordBreak2(string s, unordered_set& dict, unordered_map> cache) {
if (cache.count(s))
return cache[s];
vector ans;
if (s.empty()) {
ans.push_back(string());
return ans;
}
for (int len = 1; len <= s.size(); len++) {
string prefix = s.substr(0, len);
if (dict.count(prefix)) {
string suffix = s.substr(len);
vector segments = wordBreak2(suffix, dict, cache);
//始终注意segments是所有能拆分可能性的集合，即一个segments里就有一个拆分答案
for (int i = 0; i < segments.size(); i++) {
if (segments[i].empty())
ans.push_back(prefix);
else
ans.push_back(prefix + " " + segments[i]);
}
}
}
cache[s] = ans;
return ans;
}
Edit Distance
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zXfyOAVp-1660054528898)(C:Users13415AppDataRoamingTyporatypora-user-imagesimage-20220809075641098.png)]
E(i,j)让i,j之前都相等的最小操作数
E(i,j)=E(i,j-1)+1 增加j和j-1的相差的那个
E(i,j)=E(i-1,j)+1 删除i与j-1增加的那个字符
E(i,j)=E(i-1,j-1)+1 ,str1(i)!=str2(j)
=E(i-1,j-1)+ 0 ,str1(i)==str2(j)
int E[100][100];
int stredit(string s1, string s2) {
int len1 = s1.size();
int len2 = s2.size();
for (int i = 0; i <= len1; i++)
for (int j = 0; j <= len2; j++)
E[i][j] = 0;
for (int i = 0; i <= len1; i++)
E[i][0] = i;
for (int j = 0; j <= len2; j++)
E[0][j] = j;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
int p = 1;
if (s1[i-1] == s2[j-1])
p = 0;
E[i][j] = min({ E[i - 1][j - 1] + p, E[i][j - 1] + 1,E[i - 1][j] + 1 });
}
}
int ans = E[len1][len2];
return ans;
}
Edit Distance Trace
stack tracex,tracey;
void trace(int E[100][100],int m,int n,string s1,string s2) {
if (m < 1 || n < 1)
return;
int p = 1;
if (s1[m - 1] == s2[n - 1])
p = 0;
if (E[m][n] == E[m - 1][n - 1] + p) {
tracex.push(m - 1), tracey.push(n - 1);
trace(E, m - 1, n - 1, s1, s2);
}
else {
if (E[m][n] == E[m][n - 1] + 1) {
tracex.push(m), tracey.push(n - 1);
trace(E, m, n - 1, s1, s2);
}
else {
tracex.push(m - 1), tracey.push(n);
trace(E, m - 1, n , s1, s2);
}
}
}
