【算法】动态规划笔记

【算法】动态规划笔记

动态规划:

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

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

  • 递归写法
  • 递推写法

最大连续子序列和

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

最长不下降子序列(LIS)

  • 求一个序列的最长的子序列(可以不连续),使得这个子序列是不下降的
  • dp[i]表示必须以a[i]结尾的最长不下降子序列的长度
  • dp[i] = max{1, dp[j] + 1}; // j从1 ~ i-1 且必须满足a[j] <= a[i]

最长公共子序列(LCS)

  • 给定两个字符串或者数字序列A和B,求一个字符串,使得这个字符串是A和B的最长公共部分(子序列可以不连续)
  • dp[i][j]表示A的第i位之前和B的第i位之前的这两个序列的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 <= n, 1 <= j <= m)

最长回文子串

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

DAG最长路

背包问题

  • 多阶段动态规划问题:有一类动态规划可解的问题,它可以描述成若干个有序的阶段,且每个阶段的状态有关,一般把这类问题称为多阶段动态规划问题

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] }
  • 一维:

完全背包问题

  • 有n种物品,每种物品的单件重量为w[i],价值为c[i]。现有一个容量为v的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品有无穷件
  • 递推方程:dp[i][j] = max(dp[i-1][v], dp[i][j-w[i]] + c[i])
  • 和01背包不同,这里的j的枚举顺序为正向枚举,而且是dp[i][j-w[i]]

蓝桥杯 ADV-205算法提高 拿糖果(动态规划)

问题描述
妈妈给小B买了N块糖!但是她不允许小B直接吃掉。
  假设当前有M块糖,小B每次可以拿P块糖,其中P是M的一个不大于根号下M的质因数。这时,妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
  现在小B希望知道最多可以拿多少糖。
输入格式
  一个整数N
输出格式
  最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000

分析:动态规划问题~~首先呢~创建一个满足不大于根号下最大值MAXN的素数表,然后对素数表里面的数逐个遍历~
构建一个dp[i]数组,表示当糖果数量为i的时候所能拿的最多的糖果数量~
对于dp[i]的值:因为小B只能每次拿不大于根号下i的质因数,遍历素数表中满足条件的素数(prime[j] <= sqrt(i) && i % prime[j] == 0),更新dp[i]的值为(dp[i-2*prime[j]] + prime[j])的最大值~
即:dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);

 

蓝桥杯 ALGO-21算法训练 装箱问题(动态规划,01背包)

问题描述
  有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。
  要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入格式
  第一行为一个整数,表示箱子容量;
  第二行为一个整数,表示有n个物品;
  接下来n行,每行一个整数表示这n个物品的各自体积。
输出格式
  一个整数,表示箱子剩余空间。
样例输入
24
6
8
3
12
7
9
7
样例输出
0

分析:dp[i][j]表示前i件物品选则部分装入体积为j的背包后,背包总共所占的最大体积,
一共有n件物品,那么dp[n][v]就是前n件物品选择部分装入体积为v的背包后,背包总共占有的最大体积
1.当当前输入的物品体积大于背包容量,则不装入背包,dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量,考虑装或者不装两种状态,取体积最大的那个:dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);

 

蓝桥杯 ADV-202算法提高 最长公共子序列(动态规划)

问题描述
  给定两个字符串,寻找这两个字串之间的最长公共子序列。
输入格式
  输入两行,分别包含一个字符串,仅含有小写字母。
输出格式
  最长公共子序列的长度。
样例输入
abcdgh
aedfhb
样例输出
3
样例说明
  最长公共子序列为a,d,h。
数据规模和约定
  字串长度1~1000。
分析:求最长公共子序列,用动态规划~只需建立一个长宽为两个字符串长度+1的二维数组~dp[i][j]表示String a的前i个字符构成的字符串和String b的前j个字符构成的字符串这两者得到的最长公共子序列的长度为dp[i][j]~~~所以第0行和第0列所有的数都为0~
根据递推公式:
Snip20160525_13

按一行一行的顺序填入数~
Snip20160525_9=>Snip20160525_10=>

Snip20160525_11=>Snip20160525_12

最后一个格子的长度就是两个字符串的最长公共子序列的长度~~

蓝桥杯 ADV-156算法提高 分分钟的碎碎念(动态规划)

问题描述
  以前有个孩子,他分分钟都在碎碎念。不过,他的念头之间是有因果关系的。他会在本子里记录每一个念头,并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子,你一定会被互相穿梭的箭头给搅晕,现在他希望你用程序计算出这些念头中最长的一条因果链。
  将念头从1到n编号,念头i来源于念头from[i],保证from[i]<i,from[i]=0表示该念头没有来源念头,只是脑袋一抽,灵光一现。
输入格式
  第一行一个正整数n表示念头的数量
  接下来n行依次给出from[1],from[2],…,from[n]
输出格式
  共一行,一个正整数L表示最长的念头因果链中的念头数量
样例输入
8
0
1
0
3
2
4
2
4
样例输出
3
样例说明
  最长的因果链有:
  1->2->5 (from[5]=2,from[2]=1,from[1]=0)
  1->2->7 (from[7]=2,from[2]=1,from[1]=0)
  3->4->6 (from[6]=4,from[4]=3,from[3]=0)
  3->4->8 (from[8]=4,from[4]=3,from[3]=0)
数据规模和约定
  1<=n<=1000
分析:建立一个与from数组等长的数组dp,dp[i]表示当前序号能满足构成的最长的长度,dp[i]的值可以由dp[from[i]]+1得到~

蓝桥杯 ALGO-11算法训练 瓷砖铺放(递归/动态规划)

问题描述
  有一长度为N(1<=N<=10)的地板,给定两种不同瓷砖:一种长度为1,另一种长度为2,数目不限。要将这个长度为N的地板铺满,一共有多少种不同的铺法?
  例如,长度为4的地面一共有如下5种铺法:
  4=1+1+1+1
  4=2+1+1
  4=1+2+1
  4=1+1+2
  4=2+2
  编程用递归的方法求解上述问题。
输入格式
  只有一个数N,代表地板的长度
输出格式
  输出一个数,代表所有不同的瓷砖铺放方法的总数
样例输入
4
样例输出
5

用递归的方法解:

用动态规划的方法解: