入坑动态规划 Dynamic Programming(算法课堂笔记记录)

动态规划 Dynamic Programming

虽然动态规划也是一种穷举，但相比于普通的穷举，它显得更高效。
动态规划主要用于求优化问题，由美国数学家贝尔曼(R. Bellman)提出。这位数学家还提出了动态规划方程(贝尔曼方程)，目前在强化学习和基因比较上都有一定的应用和前景。
在一定程度上，DP≈猜+记忆+递归，“猜”用于构建递归，而“记忆”则用于求解递归。

举个栗子

如何用动态规划实现求斐波那契数列第n位？
伪代码如下:

def fib(n):
	dp={}  # 初始化一个字典，用于存放键值对，键是位，值是该位对应的数值
	for k in range(n):
		if k <= 1:
			dp[k] = k  # 假设存在第0位，第0位为0，第1位为1
		else:
			dp[k] = dp[k-1] + dp[k-2]
	return dp[-1]	

这里的猜，就是指猜斐波那契数列第n位的结果是怎么来的，第n位是第n-1位和第n-2位的和相加所得到(当然，第0位是0，第1位是1已经设置好，由代码的第一个if判断就可以知道)。而这里的 记忆，就是代码刚开始设置的这个字典，因为这个算法是DFS， 所以会把前面的位先计算出来，一位一位逐渐算到第n位，而前面的位计算得到的结果直接存入字典dp，第n位只需在字典中查找它的前两位即可。这里的递归， 我便不再赘述。

再举个栗子

求最长递增子序列。
假设 A = [18,17,19,6,11,21,23,15]，输出一个其中的最长的递增子序列。例如[6, 11, 21, 23]。

1. 建立子问题递归关系(猜)：
   dp[i] = MAX(dp[j] + 1), (j∈[0,i-1], A[j] <= A[i])
2. 建表(记忆): 为了方便计算，在处理时，先给A第一位添加一个无穷小

i	0	1	2	3	4	5	6	7	8
A[i]	-∞	18	17	19	6	11	21	23	15
dp[i]	null	[0,1]	[0,2]	[0,2,3]	[0,4]	[0,4,5]	[0,4,5,6]	[0,4,5,6,7]	[0,4,5,8]

至于实现，可以自己尝试一下

一入DP深似海，以后碰到DP的题目，再加更

本文地址：https://blog.csdn.net/weixin_45439696/article/details/110469098