DP(动态规划)的初步学习-第一部分
Today is the fifth day of the course.
Note:
dp是什么？
动态规划（DP）不是某种具体算法，而是一种思想。
核心在于：把大问题转化为小问题，利用小问题的解，推断出大问题的解。
什么是状态？
例子
《硬币问题》
Luogu-B3635
今天你手上有无限的面值为1,5,11 元的硬币。
给定n，问：至少用多少枚硬币，可以恰好凑出n 元？
思考
用f[x]表示多少钱的时候最小的硬币数，f[x]由上一次选择的最小硬币数+1得到，所以我们只需要找到上一次选择的硬币+1的最小值就可以了。故有状态转移方程：
《凑字》
现在有一篇文章是一个字，你可以添加一个字或者复制整个文章再粘贴（即字数翻倍）。说人话就是可以使一个数字加1或者×2
求码出n字的最小次数
数组f[x],x表示码出x字所需的最小增加次数，因为x字要么是加以得来，要么是×2得来。
所以如果x是奇数，那么他的次数为:
如果x是偶数，那么他可能是+1得到的，也可能是×2得到的，所以有：
所以状态转移方程为：
初步总结：状态
硬币问题中，要表达“我们需要凑出n 元钱”这个局面，可以设计状态：“f[x] 表示凑出x 元用的最少硬币数”。
上楼梯问题中，设计状态：“f[x] 表示走上x 级的方案数”。
可见，只有大问题和小问题拥有相同的形式，才能考虑拆分子问题。
如果满足这个要求，那么我们遇到的每个子问题，都可以通过某种简洁的形式来表达。
我们把可能遇到的每种“局面”称为状态。
所以最优解的最优解就是我们要的结果，一层层下去到可以人工计算或者无需计算的开头，这就是DP
形象的说，状态就是格子，而寻找状态就是寻找格子，dp就是用之前的格子来推出之后的格子。
转移
例子
LIS(最长上升子序列)
给定一个数组a，求a中最长的上升子序列
最长上升子序列：数组中最长的那一个单调上升的子序列。
下文我们以lis指代最长上升子序列。
数组f[x]表示以a[x]结尾的lis，a[p]表示接到的数，即为小于a[x]的数。所以我们只需要把a[x]接到每一个f[p]的后即可找到lis。
所以只要a,p满足p<x,a[p]<a[x],然后枚举f[p]+1的最大值就是f[x]的最优解。
此时我们已经找到了状态以及状态转移方程:
小结：状态和转移
一个dp题，应该经历2个过程：
- 设计状态。把面临的每一个问题，表达成一个个「状态」。
- 设计转移。写出状态转移方程，从而利用小问题的解推出大问题的解。
可以通俗的说：大事化小，小事化了
dp的两种实现方式
dp的递推形式可以从过去推到现在，也可以从现在推到未来，时间复杂度和空间都是一样的，只是写法不同罢了，就像dp可以用递推实现也可以用记忆化搜索实现。
可以称为“我从哪里来”和“我到哪里去”
刚刚的《硬币问题》也可以使用“我到哪里去”实现：
《Lis》问题也可以：
小结：设计转移
我从哪里来：对于一个没有求出解的状态，利用能走到它的状态，来得出它的解。
我到哪里去：对于一个已经求好了解的状态，拿去更新它能走到的状态。
两者只有写法上的区别，没有效率上的区别（根据状态和状态转移方程来选择写法）
dp总结
dp可以分为3步：
- 设计状态
- 找到状态转移方程
- 在“我从哪里来”和“我到哪里去”中选择好写的一个实现代码
完成后你就完美的切掉了一道dp题，congratulations !
dp与贪心的区别
通过一个例题来说明：
你手上有1 个苹果，他每次施法可以让苹果数量+1 或×2。
请问你至少需要多少次施法，才能恰好得到n 个苹果。
和刚刚的《凑字》问题是一模一样的，dp：
而贪心要好写一些：
可以看到，贪心是直接使用了f[x/2]+1而不去确认是否有更优解，贪心是对当前状态下的最优解而不是全局最优解，所以人们说贪心是“目光短浅”的。但是对于这道题，贪心更快也更好些。而dp开头讲过,dp是把大问题转化为小问题，利用小问题的解，推断出大问题的解。
这便是dp与贪心的区别，他们之间没有目前的分界线，可能一道题贪心和dp都占了。
贪心算法和动态规划最大的不同在于：贪心法并不是首先寻找子问题的最优解，然后在其中进行选择，而是首先做出一次「贪心」选择——在当时（局部）看来最优的选择，然后求解选出的子问题，从而不必费心求解所有可能相关的子问题。
—— 《算法导论》
欢迎查看第二部分哦。
This article was written on July 21, 2022 at 13:41.
