动态规划学习
2021/11/4 23:11:51
本文主要是介绍动态规划学习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
动态规划
动态规划问题简称为DP问题(dynamic problem)
- 规模是否可缩小
- 用函数思想构造一个状态表达式(黑盒思路)
- 构造状态转移
- 优化(memorization/tabulation)
e.g. Longest Common Subsequence(LCS)
- 规模是否可缩小
- 用函数思想构造一个状态表达式(黑盒思路)
- lcs(str1, str2, m, n)
- 构造状态转移
- 1+lcs(m-1, n-1)
- max(lcs(m-1, n), lcs(m, n-1))
- 优化(memorization/tabulation)
- overlapping
1 递归树 Recursive Tree
def lcs(str1, str2, m, n): if m == 0 or n == 0: return 0 if str1[m-1] == str2[n-1]: case1 = 1 + lcs(str1, str2, m-1, n-1) return case1 else: case2 = max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1)) return case2
In:
str1 = 'abcdef' str2 = 'afbce' m = len(str1) n = len(str2) res = lcs(str1, str2, m, n) print(res)
Out:
4
存在overlapping的问题
2 memoization
改进(自上而下):
def lcs(str1, str2, m, n): #m, n 规模的问题对应的矩阵坐标为m-1, n-1 if m == 0 or n == 0: dp[m][n] = 0 return 0 if dp[m][n] != -1: return dp[m][n] if str1[m-1] == str2[n-1]: case1 = 1 + lcs(str1, str2, m-1, n-1) dp[m][n] = case1 return case1 else: case2 = max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1)) dp[m][n] = case2 return case2
In:
str1 = 'bd' str2 = 'abcd' m = len(str1) n = len(str2) dp = [[-1] * (n+1) for _ in range(m+1)] res = lcs(str1, str2, m, n) print(res) print(dp)
Out:
2 [[-1, 0, -1, 0, -1], [-1, -1, 1, 1, -1], [-1, -1, -1, -1, 2]]
3 tabulation
改进(自下而上):
def lcs(str1, str2, m, n): dp = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): left = dp[i][j-1] up = dp[i-1][j] left_up = dp[i-1][j-1] if str1[i-1] == str2[j-1]: dp[i][j] = left_up + 1 else: dp[i][j] = max(left, up) #print(dp) return dp[m][n]
4 空间优化
4.1 只用两行矩阵
def lcs(str1, str2, m, n): dp = [[0] * (n+1) for _ in range(2)] #这里发生了变化,只需要两行来推断下面的表格 for i in range(1, m+1): for j in range(1, n+1): #代码中的dp[0]代表前一行 #代码中的dp[1]代表当前行 left = dp[1][j-1] up = dp[0][j] left_up = dp[0][j-1] if str1[i-1] == str2[j-1]: dp[1][j] = left_up + 1 else: dp[1][j] = max(left, up) #处理完一行,把当前行的值覆盖前一行 for k in range(1, n+1): dp[0][k] = dp[1][k] #print(dp) return dp[m][n]
5 小结
tabulation | memoization | |
---|---|---|
状态转移 | 不好想 | 利用递归的思想容易想 |
代码 | 需要考虑矩阵的位置关系, 不好写 | 容易编写 |
速度 | 直接通过访问前一个状态的结果计算下一个状态 速度快 | 多层递归,由于递归的层数在系统中是有限制的,所以有时候会慢,甚至达到限制 |
表内数据 | 每一个元素都要填充数据 | 只有需要的位置才会被填充上数据 |
下一个状态
速度快 | 多层递归,由于递归的层数在系统中是有限制的,所以有时候会慢,甚至达到限制 |
| 表内数据 | 每一个元素都要填充数据 | 只有需要的位置才会被填充上数据 |
这篇关于动态规划学习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现