Dotcpp  >  编程教程  >  动态规划  >  什么是线性DP?

什么是线性DP?

点击打开在线编译器,边学边练

一、什么是线性?

越是基础的概念,越应该有一个透彻的理解,才能对上层问题有直接了当的理解。比如对线性分割器,你对线性有透彻的理解,一看这个名字就大概知道它是怎么回事了。


1. 几何理解:线性关系就是直线关系

现在你可以想象一条曲线S,它可以是直的也可以是弯的,然后你得承认一个事实:曲线S上的任意一点,都可以由曲线S 上其他的任意一点沿着曲线移动而来。

然后我们来看这个移动。在二维坐标平面,移动就意味着横坐标轴和纵坐标轴的变化,如果两者的变化成一个倍数关系,即横坐标变化了2,纵坐标就变化了6;而横坐标变化了8,纵坐标就变化了24(当然这个倍数也可以是无穷,这时候对应这水平或竖直线);像这种移动,则是在一条直线上的移动,否则,就是曲线上的移动。

都是移动,为啥直线移动比较特别呢?因为这种移动,不同坐标在放缩和叠加上保持一致,扩大而说就是 不同维度在放缩和叠加上保持一致。

好了到这里就可以回到最初的问题了,什么是线性?就是沿直线走的特性!!!

如何理解 “沿直线走的特性” ”不同维度的放缩和叠加保持一致“ ?

比如,一个线性信号处理系统,我们都知道它的定义就是:信号经过叠加后经过系统和经过系统后在叠加是等价的,那么这个系统就是线性系统。

这按照 沿直线走的特性 来理解的话,就是这个系统是走直线的,就是输入和输出是走直线的,即输入和输出放缩和叠加上保持一致。输入扩大了n倍,那么输出也会扩大n倍,输入是两个信号的叠加,那么输出也会是两个相应输出信号的叠加。


2. 数值理解:线性就是只进行放缩和叠加

为什么只进行放缩和叠加就是线性呢?因为直线的坐标进行只进行放缩和叠加的话,不同坐标是保持一致性的。

再比如,n维线性空间,为啥加线性空间呀?线性二字体现在哪里呢?三个基向量(1, 1, 0, 0)、(0, 1, 1, 0)、(0, 0, 1, 1) span的空间为一个三维线性空间,这时候这个空间的坐标单位就是上面三个向量,而一个向量它又是由四个数组成,线性就体现在这四个数中相应位置的数只进行了放缩和叠加,没错,线性就体现在这里。


二、什么是线性DP?

在线性结构上进行状态转移,目标函数为特定变量的线性函数,目的是求目标函数的最大值或最小值。

1. 线性DP定义:

这里的定义只是一个概述,所谓的线性DP是指我们的递推方程是存在一个线性的递推关系。可以是一维线性的、二维线性的、三维线性的、…。

最长上升子序列模型属于线性DP。


2. DP解题套路

(1)把问题分解成若干子问题;

(2)根据题意列出状态转移方程;

(3)找出边界;

(4)递推求解。


DP问题核心就是枚举,枚举出问题所有可能的情况,然后取最优解。DP算法实际上就是设计一种思路(状态转移方程),让程序能高效率地运行出所求结果。



知识点标签:动态规划


本文固定URL:https://www.dotcpp.com/course/997

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)