入坑动态规划 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]。
- 建立子问题递归关系(猜):
dp[i] = MAX(dp[j] + 1), (j∈[0,i-1], A[j] <= A[i]) - 建表(记忆): 为了方便计算,在处理时,先给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
上一篇: 怎么办?人工智能可能引发公众的强烈反对