Notion 博客 一个NotionNext搭建的博客
数据库系统概论
大数据原理与应用
javaWeb应用开发基础教程
python
毕业设计
大数据技术综合应用
实训-航空数据系统
java面向对象程序设计
数据结构
算法分析与设计
SPARK
Python爬虫大数据采集与挖掘
云计算
概率论与数理统计
数字逻辑
计算机网络
计算机组成原理
linux
操作系统
人工智能导论
数据仓库与数据挖掘
数据可视化
大数据安全与隐私保护
c语言
C++
[第三章]动态规划
自底向下
最优子结构
承接子问题
简介
基本思想：分解成若干个子问题，产生许多重复问题；记录中间值，节省时间
基本结构
- 最优子结构
- 重叠子问题
- 备忘录方法
→ 一般求极值问题
矩阵连乘问题
完全加括号的矩阵连乘积
由于矩阵相乘不满足交换律，即a*b*c≠b*c*a
故不同相乘需要的算力不同
穷举法
最长公共子序列
X Y Z,Z是X、Y的公共子序列
- X最后=Y最后=Z最后，则Zk-1 是Xm-1 和Yn-1的公共子序列
- X最后≠Y最后=Z最后，则Zk-1 是Xm-1 和Y的公共子序列
- Y最后≠X最后=Z最后，则Zk-1 是X 和Yn-1 的公共子序列
凸多边形最优三角部分
多边形游戏
n个顶点n条边，每个顶点一个数字，每个边是“+”或“*”
- 设给的多边形顶点为op[i]，边为v[i]，i=1~n
- 设m1是对子链p(i,s)的任意一种合并方式得到的值，设a,b是最小值和最大值，则a≤m≤b。划分之后剩下的
图像压缩
- 一个字节八位数
- l[i]=字数
- b[i]=n，n指2^n大小的字来存储
电路布线
(i)排列从1到n
流水作业调度
- Johnson
01背包问题
课后题
int a[n]，n大约 到n^9
int a[n][n]，n大约到n^5
- 假设已经找到一段最小值，该最小值开始时间为i，结束时间为k
- 列出从i到k需要的解的式子
- 然后找min（本式子加下一个项（递归））
- 优化算法：剪枝（减少肯定不行的）
- c++变量可以出现在数组[]的下标，c语言不可以
编程技巧
- 前缀/后缀数组
t[i] 1 3 5 7 9 11数组
tt[i] 1 4 9 16 25 36前缀数组
不用嵌套两层循环便可获取当前数组中ai到aj的加和
dp[i] = min {dp[i] , dp[j]+ fei(i,j) }
- 如果每次循环都会改变循环条件，可以用数组（也可能是二维数组）记录当前值并用于判断
Prev
[第二章]递归与分治策略
Next
[第四章]贪心算法
Loading...