一、什么是线性?
越是基础的概念,越应该有一个透彻的理解,才能对上层问题有直接了当的理解。比如对线性分割器,你对线性有透彻的理解,一看这个名字就大概知道它是怎么回事了。
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算法实际上就是设计一种思路(状态转移方程),让程序能高效率地运行出所求结果。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程