线性动态规划

线性动态规划是具有线性阶段划分的动态规划算法，也称线性DP。若状态包含多个维度，则每个维度都是线性划分的阶段，也属于线性DP，如下图所示：

线性动态规划-01.png

序列问题

最长上升子序列剑指 Offer II 095. 最长公共子序列

Longest Increasing Subsequence问题，最长上升子序列，其一般为求序列A最长上升或下降子序列。

求解过程：dp[i]表示以A序列i为结尾的最长上升子序列的长度，则有转移方程为：
$dp[i]=Math.max(dp[j]+1, dp[i]),\ where\ 0\leq j < i\ and\ a[j] < a[i]$

最长公共子序列剑指 Offer II 095. 最长公共子序列

Longest Common Subsequence问题，最长公共子序列，求取两个序列A和B的最长公共子序列。

求解过程：dp[i,j]表示子串A[1,...,i]与B[1,...,j]的最长公共子序列的长度，转移方程为：
$dp[i,j]=Math.max(dp[i-1,j],dp[i,j-1])\ \ if\ A[i]!=B[j]\\ dp[i,j]=Math.max(dp[i-1,j],dp[i,j-1],dp[i-1][j-1]+1)\ \ if\ A[i]==B[j]\\$

字符串编辑距离

字符串编辑距离 72. 编辑距离

Levenshtein问题，字符串编辑距离，求取从字符串A到字符串B的编辑单个字符所需的最少次数，其中编辑单个字符可以有删除、替换、插入。

求解过程：dp[i,j]表示字符串A的前 $i$ 个位置到字符串B的前 $j$ 个位置的编辑距离，转移方程为：
$dp[i,j]=Math.min(dp[i-1,j-1],Math.min(dp[i-1,j],dp[i,j-1]))+1\ if\ A[i]!=B[i]\\ dp[i,j]=dp[i-1,j-1]\ if\ A[i]==B[i]$

最大和问题

最大子序列和 53. 最大子数组和

最大子序列和问题，对给定序列a[1],a[2],a[3],...,a[n]寻找它的连续的最大和子数组。

求解过程：dp[i]表示保存前 $i$ 最大的连续子数组，转移方程为：
$dp[i]=dp[i-1]+a[i]\ if\ dp[i-1]>=0\\ dp[i]=a[i]\ if\ dp[i-1]<0$

最大子矩阵和面试题 17.24. 最大子矩阵

最大子矩阵和问题，给定一个n行m列的整数矩阵a，现在要求a的一个子矩阵，使其各元素之和为最大。

求解过程：由于最终的子矩阵一定在某两行之间，所以可以先对数据进行处理降低时间复杂度，即 $b[i,j]=\sum_{k=1}^{j}a[i,k]$ 。这样的话，最大子矩阵的搜索问题就转移到了当两行确定是去算两行i和j之间的最大值dp[k]，转移方程为：
$dp[i]=dp[i-1]+(b[i] - b[j-1])\ if\ dp[i-1]>=0\\ dp[i]=b[i] - b[j-1]\ if\ dp[i-1]<0$

数字三角形剑指 Offer II 100. 三角形中最小路径之和

数字三角形问题，给定一个如下形式的数字三角形a，现在要从左上角走到最底层，每一步只能走到相邻的结点，求经过的结点的最大数字和/最小数字和。

求解过程：dp[i,j]表示走到第i行第j列的最大/最小和，转移方程为：
$dp[i,j] = Math.max/min(dp[i-1,j],dp[i-1,j-1])+a[i,j]$

最后编辑于：2022.10.10 13:58:13

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

线性动态规划