【概述】

線性動(dòng)態(tài)規(guī)劃，是較常見的一類動(dòng)態(tài)規(guī)劃問題，其是在線性結(jié)構(gòu)上進(jìn)行狀態(tài)轉(zhuǎn)移，這類問題不像背包問題、區(qū)間DP等有固定的模板。

線性動(dòng)態(tài)規(guī)劃的目標(biāo)函數(shù)為特定變量的線性函數(shù)，約束是這些變量的線性不等式或等式，目的是求目標(biāo)函數(shù)的最大值或最小值。

因此，除了少量問題（如：LIS、LCS、LCIS等）有固定的模板外，大部分都要根據(jù)實(shí)際問題來推導(dǎo)得出答案。

【常見問題】

序列問題：點(diǎn)擊這里

字符串編輯距離：點(diǎn)擊這里

最大和問題：點(diǎn)擊這里

【例題】

1.序列問題：

Monkey and Banana（HDU-1069）(LIS)：點(diǎn)擊這里

求最長(zhǎng)不下降序列（信息學(xué)奧賽一本通-T1259）(LIS)：點(diǎn)擊這里

最長(zhǎng)上升子序列（信息學(xué)奧賽一本通-T1289）(LIS)：點(diǎn)擊這里

怪盜基德的滑翔翼（信息學(xué)奧賽一本通-T1286）(LIS)：點(diǎn)擊這里

登山（信息學(xué)奧賽一本通-T1283）(LIS)：點(diǎn)擊這里

攔截導(dǎo)彈（信息學(xué)奧賽一本通-T1260）(LIS)：點(diǎn)擊這里

攔截導(dǎo)彈（信息學(xué)奧賽一本通-T1289）(LIS)：點(diǎn)擊這里

導(dǎo)彈攔截（洛谷-P1020）(二分+LIS)：點(diǎn)擊這里

友好城市（信息學(xué)奧賽一本通-T1289）(排序+LIS)：點(diǎn)擊這里

合唱隊(duì)形（洛谷-P1091）(兩遍 LIS)：點(diǎn)擊這里
同題：合唱隊(duì)形（信息學(xué)奧賽一本通-T1264）：點(diǎn)擊這里

Eating Together（POJ-3670）(兩遍 LIS)：點(diǎn)擊這里

Super Jumping! Jumping! Jumping!（HDU-1087）(LIS 的和)：點(diǎn)擊這里

最大上升子序列和（信息學(xué)奧賽一本通-T1285）(LIS?的和)：點(diǎn)擊這里

Common Subsequence（HDU-1159）(LCS)：點(diǎn)擊這里

最長(zhǎng)公共子序列（信息學(xué)奧賽一本通-T1289）(LCS)：點(diǎn)擊這里

回文字符串（51Nod-1092）(LCS)：點(diǎn)擊這里

公共子序列（信息學(xué)奧賽一本通-T1297）(LCS)：點(diǎn)擊這里

最長(zhǎng)公共子上升序列（信息學(xué)奧賽一本通-T1306）(LCIS)：點(diǎn)擊這里

2.字符串編輯距離

編輯距離（信息學(xué)奧賽一本通-T1276）：點(diǎn)擊這里

計(jì)算字符串距離（信息學(xué)奧賽一本通-T1298）：點(diǎn)擊這里

相似基因（洛谷-P1140）(字符串距離+模擬)：點(diǎn)擊這里

3.求和問題

序列相關(guān)

Max Sum（HDU-1003）(序列最大和)：點(diǎn)擊這里

糖果（信息學(xué)奧賽一本通-T1299）(序列最大和)：點(diǎn)擊這里

大盜阿福（信息學(xué)奧賽一本通-T1301）(子序列和)：點(diǎn)擊這里

小a的子序列（2019牛客寒假算法基礎(chǔ)集訓(xùn)營(yíng) Day1-F）(子序列和)：點(diǎn)擊這里

Milking Time（POJ-3616）(貪心+序列最大和)：點(diǎn)擊這里

乘積最大（信息學(xué)奧賽一本通-T1275）(子序列最大乘積)：點(diǎn)擊這里

Maximum sum（信息學(xué)奧賽一本通-T1305）(最大子段和)：點(diǎn)擊這里

矩陣相關(guān)

最低通行費(fèi)（信息學(xué)奧賽一本通-T1287）(矩陣最小和)：點(diǎn)擊這里

Vasya And The Mushrooms（CF-1016C）(矩陣最大和)：點(diǎn)擊這里

摘花生（信息學(xué)奧賽一本通-T1284）(矩陣最大和)：點(diǎn)擊這里

命運(yùn)（HDU-2571）(矩陣最大和)：點(diǎn)擊這里

最大正方形（洛谷-P1387）(最大子矩陣)：點(diǎn)擊這里

最大子矩陣（信息學(xué)奧賽一本通-T1282）(最大子矩陣)：點(diǎn)擊這里

Likecloud-吃、吃、吃（洛谷-P1508）(最大子矩陣和)：點(diǎn)擊這里

最大子矩陣（信息學(xué)奧賽一本通-T1224）(最大子矩陣和)：點(diǎn)擊這里

創(chuàng)意吃魚法（洛谷-P1736）(最大子矩陣和)：點(diǎn)擊這里

方格取數(shù)（信息學(xué)奧賽一本通-T1277）(矩陣最大路徑)：點(diǎn)擊這里

數(shù)字三角形相關(guān)

數(shù)塔（HDU-2084）：點(diǎn)擊這里

數(shù)字三角形（洛谷-P1216）：點(diǎn)擊這里
同題：三角形最佳路徑問題（信息學(xué)奧賽一本通-T1288）：點(diǎn)擊這里

數(shù)字金字塔（信息學(xué)奧賽一本通-T1258）：點(diǎn)擊這里

免費(fèi)餡餅（HDU-1176）(數(shù)字三角形思想)：點(diǎn)擊這里

櫥窗布置（信息學(xué)奧賽一本通-T1279）(數(shù)字三角形思想)：點(diǎn)擊這里

雞蛋的硬度（信息學(xué)奧賽一本通-T1300）(數(shù)字三角形思想)：點(diǎn)擊這里

4.其他

The Cow Lexicon（POJ-3267）(字符匹配+線性DP)：點(diǎn)擊這里

超級(jí)樓梯（HDU-2040）(分治+線性DP)：點(diǎn)擊這里

Problem Solving（POJ-3265）(分治+線性DP)：點(diǎn)擊這里

股票買賣（信息學(xué)奧賽一本通-T1302）(分治+線性DP)：點(diǎn)擊這里

小b和排序（51Nod-2484）(分治+線性DP)：點(diǎn)擊這里

數(shù)的劃分（洛谷-P1025）(分治+線性DP)：點(diǎn)擊這里
同題：數(shù)的劃分（信息學(xué)奧賽一本通-T1304）：點(diǎn)擊這里

奇怪的電梯（洛谷-P1135）(分治+線性DP)：點(diǎn)擊這里
同題：奇怪的電梯（信息學(xué)奧賽一本通-T1360）點(diǎn)擊這里

Race（LightOJ-1326）(打表+線性DP)：點(diǎn)擊這里

Crossing River（信息學(xué)奧賽一本通-T1232）(貪心+線性DP)：點(diǎn)擊這里

Telephone Wire（POJ-3612）(預(yù)處理+線性DP)：點(diǎn)擊這里

山區(qū)建小學(xué)（信息學(xué)奧賽一本通-T1197）(預(yù)處理+線性DP)：點(diǎn)擊這里

挖地雷（信息學(xué)奧賽一本通-T1262）(遞歸輸出+線性DP)：點(diǎn)擊這里

機(jī)器分配（信息學(xué)奧賽一本通-T1266）(遞歸輸出+線性DP)：點(diǎn)擊這里

尼克的任務(wù)（洛谷-P1280）(逆序+線性DP)：點(diǎn)擊這里

復(fù)制書稿（信息學(xué)奧賽一本通-T1278）(前綴和+線性DP)：點(diǎn)擊這里

判斷整除（信息學(xué)奧賽一本通-T1195）(數(shù)論基礎(chǔ)+線性DP)：點(diǎn)擊這里

Increasing Frequency（CF-1082E）(區(qū)間變換技巧+線性DP)：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的动态规划 —— 线性 DP的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。