从最简单的线性DP开始
2024-10-19 17:25:25
导读 ^ _ ^
线性DP可以说是最常见的DP问题。
从本期开始,我们将从最简单的线性DP开始学起。
后面同时更新一些经典的面试题带大家更加深入的学习线性DP
如何计算动态规划的时间复杂度?
状态数 x 转移次数
理解线性
按照某种线性关系进行线性的状态的转移。
数字三角形
思路
我们先对矩阵结构进行研究
推导公式:
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510,INF=-1e9;
int n;
int a[N][N];
int f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin>> a[i][j];
for (int i = 0; i <=n; i++)
for (int j = 0; j <= n+1; j++)
f[i][j] = INF;
//记得初始化
f[1][1] = a[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <=i; j++)
f[i][j] = max(f[i-1][j] + a[i][j],f[i-1][j-1] + a[i][j]);
int res = INF;
for (int i = 1; i <= n; i++) res = max(res,f[n][i]);
cout << res << endl;
return 0;
}
总结
在学完上面的题,你一定对线性DP有了一些印象。
所谓线性dp,就是指我们的递归方程有一个明显的线性关系的,有可能是一维线性的,也可能是二维线性的。
就是我们在求dp的(动态规划)里面的每一个状态都是一个多维的状态。
多维状态有一个求的顺序,比如说背包问题,可以画出来一个矩阵,这个求的时候有一个明显的求的顺序,就是按行一行行地求,有一个明显的线性的顺序来求,这样的dp就被称为线性dp。所有这种递推顺序有一个模糊的线性的顺序的话,就被称为线性dp。
所有这种递推顺序有一个模糊的线性的顺序的话,就被称为线性dp。
谢谢你的观看!
最新文章
- 4.Git的安装
- bzoj2819 Nim
- log4j2 配置文件
- 【mysql】关于IO/内存方面的一些优化
- Ini文件操作函数
- Margin and Padding in Windows Forms Controls
- linux扩展lvm磁盘
- rpm -qs查看包信息
- 讨论IT选定的技术招聘企业几点
- Disruptor并发框架(一)简介&;上手demo
- 利用curl 实现URL监控
- 一.ArrayList原理及实现学习总结
- 五校联考 running (欧拉函数)
- du 查看文件大小
- word中怎样设置页码包含总页数
- Windows 端口占用解决
- SharePoint 修改项目的new图标显示天数
- RateLimiter
- 【LeetCode】216. Combination Sum III
- 【C/C++】void指针知多少