壹:线性DP
所谓线性DP就是简单、容易写、易看出来的DP,这类DP经常在简单题中出现。
通常在序列中用一维数组存储,矩阵中用二维数组存储。
一维例子:设 \(f_i\) 表示前 \(i\) 个数中最长连续个 1
出现的次数。
二维例子:设 \(f_{i,j}\) 表示从 \((1,1)\) 走到 \((i,j)\) 所需要用到的最少的步数。
线性DP的转移通常是较简单、易发现的。
例如:求一个序列中最长连续 1
出现的次数。
通常在序列中用一维数组存储,矩阵中用二维数组存储。
一维例子:设 \(f_i\) 表示前 \(i\) 个数中最长连续个 1
出现的次数。
二维例子:设 \(f_{i,j}\) 表示从 \((1,1)\) 走到 \((i,j)\) 所需要用到的最少的步数。
线性DP的转移通常是较简单、易发现的。
例如:求一个序列中最长连续 1
出现的次数。