【算法】动态规划笔记

将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解
动态规划会将每个求解过的子问题的解记录下来，这样下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算
可以用递归或者递推的写法实现，递归的写法又叫记忆化搜索
重叠子问题：如果一个问题可以被分解成若干个子问题，且这些子问题会重复出现，就称这个问题拥有重叠子问题。一个问题必须拥有重叠子问题，才能用动态规划去解决。
最优子结构：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称为这个问题拥有的最优子结构。最优子结构保证了动态规划中的原问题的最优解可以由子问题的最优解推导而来
动态规划与分治的区别：都是分解为子问题然后合并子问题得到解，但是分治分解出的子问题是不重叠的
动态规划与贪心的区别：都有最优子结构，但是贪心直接选择一个子问题去求解，会抛弃一些子问题，这种选择的正确性需要用归纳法证明，而动态规划会考虑所有的子问题

动态规划的递归和递推写法

递归写法

//不使用动态规划
int F(int n) {
  if(n == 0 || n == 1) return 1;
  else return F(n - 1) + F(n - 2);
}
// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)
int dp[10000];
memeset(dp, -1, sizeof(dp));
int F(int n) {
  if(n == 0 || n == 1) return 1;
  if(dp[n] != -1) return dp[n];
  else {
    dp[n] = F(n-1) + F(n - 2);
    return dp[n];
  }
}

//不使用动态规划

int F(int n) {

if(n == 0 || n == 1) return 1;

else return F(n - 1) + F(n - 2);

}

// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)

int dp[10000];

memeset(dp, -1, sizeof(dp));

int F(int n) {

if(n == 0 || n == 1) return 1;

if(dp[n] != -1) return dp[n];

else {

dp[n] = F(n-1) + F(n - 2);

return dp[n];

}

递推写法

// 数塔为例
// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])
// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j]   [(j从1~n)]
// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]
// f[i][j]为第i行j列数字的大小
// 采用自底向上递推的方法
// 数组从1开始作为下标存储
for(int i = n - 1; i >= 1; i--) {
  for(int j = 1; j <= i; j++)
    f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
return f[1][1];

// 数塔为例

// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])

// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j] [(j从1~n)]

// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

// f[i][j]为第i行j列数字的大小

// 采用自底向上递推的方法

// 数组从1开始作为下标存储

for(int i = n - 1; i >= 1; i--) {

for(int j = 1; j <= i; j++)

f[i][j] += max(f[i+1][j], f[i+1][j+1]);

}

return f[1][1];

最大连续子序列和

给定序列，求连续的子序列要求和最大，求最大的和为多少
dp[i]表示以a[i]作为末尾的连续序列的最大和（a[i]必须是末尾被选的数啊啊），dp数组中所有的数据的最大值就是所求
dp[0]初始化为a[0]，dp数组从1生成到n-1
因为a[i]一定是所选序列的末尾，所以分为两种情况：
- a[i]开始，a[i]结束
- 某数开始，到a[i]结束（最大和是dp[i-1] + a[i]）
所以递推方程为dp[i] = max(a[i], dp[i-1]+a[i]);
dp数组中所有的数据的最大值就是所求：maxn = max(dp[i], maxn);

// a数组从下标0开始
dp[0] = a[0];
int maxn = a[0];
for(int i = 1; i < n; i++) {
  dp[i] = max(a[i], dp[i-1]+a[i]);
  maxn = max(dp[i], maxn);
}
printf("%d", maxn);

// a数组从下标0开始

dp[0] = a[0];

int maxn = a[0];

for(int i = 1; i < n; i++) {

dp[i] = max(a[i], dp[i-1]+a[i]);

maxn = max(dp[i], maxn);

}

printf("%d", maxn);

最长不下降子序列（LIS）

求一个序列的最长的子序列（可以不连续），使得这个子序列是不下降的
dp[i]表示必须以a[i]结尾的最长不下降子序列的长度，dp数组中所有数据的最大值即为所求
i从0到n-1依次更新dp[i]的值，dp[i]的值需要由之前所生成的所有dp[j]递推而得（j从1到i-1），每次检查是否a[i]>=a[j]，即是否构成最长不下降子序列，如果构成，会有两种结果：
- dp[j]+1比dp[i]大，则更新dp[i] = dp[j] + 1
- dp[j]+1比dp[i]小，则dp[i]保持不变
所以递推方程为dp[i] = max{dp[i], dp[j] + 1};
dp数组中所有数据的最大值即为所求：ans = max(dp[i], ans);

int ans = 0;
for(int i = 0; i < n; i++) {
  for(int j = 1; j < i; j++) {
    if(a[i] >= a[j])
      dp[i] = max(dp[i], dp[j] + 1);
  }
  ans = max(dp[i], ans);
}

printf("%d", ans);

int ans = 0;

for(int i = 0; i < n; i++) {

for(int j = 1; j < i; j++) {

if(a[i] >= a[j])

dp[i] = max(dp[i], dp[j] + 1);

}

ans = max(dp[i], ans);

}

printf("%d", ans);

最长公共子序列（LCS）

给定两个字符串或者数字序列A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）
dp[i][j]表示A的第 i 位之前和B的第 j 位之前的这两个序列的LCS最长公共子序列的长度（下标从1开始），那么dp[lena][lenb]即为所求
递推方程：
- 当a[i] == b[j] : dp[i][j] = dp[i-1][j-1] + 1
- 当a[i] != b[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 边界：dp[i][0] = dp[0][j] = 0(0 <= i <= lena, 1 <= j <= lenb)

char a[100], b[100];
scanf("%s", a+1);
scanf("%s", b+1);
int lena = strlen(a + 1), lenb = strlen(b + 1);
for(int i = 0; i <= lena; i++) dp[i][0] = 0;
for(int j = 0; j <= lenb; j++) dp[0][j] = 0;
for(int i = 1; i <= lena; i++) {
  for(int j = 1; j <= lenb; j++) {
    if(a[i] == b[j])
      dp[i][j] = dp[i-1][j-1] + 1;
    else
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  }
}
printf("%d", dp[lena][lenb]);

char a[100], b[100];

scanf("%s", a+1);

scanf("%s", b+1);

int lena = strlen(a + 1), lenb = strlen(b + 1);

for(int i = 0; i <= lena; i++) dp[i][0] = 0;

for(int j = 0; j <= lenb; j++) dp[0][j] = 0;

for(int i = 1; i <= lena; i++) {

for(int j = 1; j <= lenb; j++) {

if(a[i] == b[j])

dp[i][j] = dp[i-1][j-1] + 1;

else

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

}

printf("%d", dp[lena][lenb]);

最长回文子串

给出一个字符串s，求s的最长回文子串的长度
dp[i][j]表示 s[i] 到 s[j] 所表示的字串是否是回文字串，值只有0和1
初始化长度1和2的值：dp[i][i] = 1, dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0，然后长度L从3到len，满足的最大长度L即为所求的ans值
递推方程：
- 当s[i] == s[j] : dp[i][j] = dp[i+1][j-1]
- 当s[i] != s[j] : dp[i][j] = 0
因为i、j如果从小到大的顺序来枚举的话，无法保证更新dp[i][j]的时候dp[i+1][j-1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举，即第一遍将长度为3的子串的dp的值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp的值…这样就可以避免状态无法转移的问题

int len = s.length();
//先把1和2长度的都初始化了
int ans = 1;
for(int i = 0; i < len; i++) {
  dp[i][i] = 1;
  if(i < len - 1 && s[i] == s[i+1]) {
    dp[i][i+1] = 1;
    ans = 2;
  }
}
//状态转移方程
for(int L = 3; L <= len; L++) {
  for(int i = 0; i + L - 1 < len; i++) {
    int j = i + L - 1;
    if(s[i] == s[j] && dp[i+1][j-1] == 1) {
      dp[i][j] = 1;
      ans = L;
    }
  }
}
printf("%d", ans);

int len = s.length();

//先把1和2长度的都初始化了

int ans = 1;

for(int i = 0; i < len; i++) {

dp[i][i] = 1;

if(i < len - 1 && s[i] == s[i+1]) {

dp[i][i+1] = 1;

ans = 2;

}

//状态转移方程

for(int L = 3; L <= len; L++) {

for(int i = 0; i + L - 1 < len; i++) {

int j = i + L - 1;

if(s[i] == s[j] && dp[i+1][j-1] == 1) {

dp[i][j] = 1;

ans = L;

}

printf("%d", ans);

背包问题

01背包问题

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个重量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件
dp[i][j]表示前i件物品恰好装入容量为j的背包所能获得的最大价值
- 不放第i件物品，则 dp[i][j] = dp[i-1][j]
- 放第i件物品，那么问题转化为前i – 1件物品恰好装入容量j – w[i]的背包中所能获得的最大价值 dp[i-1][j-w[i]] + c[i]
递推方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i]);

for(int i = 1; i <= n; i++) {
  for(int j = 1, j <= v; j++)
    if(j - w[i] >= 0) 
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);
    else
      dp[i][j] = dp[i-1][j];    
}

for(int i = 1; i <= n; i++) {

for(int j = 1, j <= v; j++)

if(j - w[i] >= 0)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);

else

dp[i][j] = dp[i-1][j];

}

一维：

for(int i = 1; i <= n; i++) {
  for(int j = v; j >= w[i]; j--)
    dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
}

for(int i = 1; i <= n; i++) {

for(int j = v; j >= w[i]; j--)

dp[v] = max(dp[v], dp[v-w[i]] + c[i]);

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版