欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-27 21:19:42
动态规划 Dynamic Programming虽然动态规划也是一种穷举,但相比于普通的穷举,它显得更高效。动态规划主要用于求优化问题,由美国数学家贝尔曼(R. Bellman)提出。这位数学家还提出了动态规划方程(贝尔曼方程),目前在强化学习和基因比较上都有一定的应用和前景。在一定程度上,DP≈猜+记忆+递归,“猜”用于构建递归,而“记忆”则用于求解递归。举个栗子如何用动态规划实现求斐波那契数列第n位?伪代码如下:def fib(n):dp={} # 初始化一个字典,用于存放键值对,键...

动态规划 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