动态规划学习
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-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南