線性模型

【例題】在一個夜黑風高的晚上，有n（n <= 50）個小朋友在橋的這邊，現在他們需要過橋，但是由于橋很窄，每次只允許不大于兩人通過，他們只有一個手電筒，所以每次過橋的兩個人需要把手電筒帶回來，i號小朋友過橋的時間為T[i]，兩個人過橋的總時間為二者中時間長者。問所有小朋友過橋的總時間最短是多少。

思路1：貪心算法。總是跑得最快的人跑回來的話，那么他在每次別人過橋的時候一定得跟過去。但是，來看一組數據 四個人過橋花費的時間分別為 1 2 5 10，按照貪心算法答案是19，但是實際答案應該是17。

具體步驟是這樣的：

第一步：1和2過去，花費時間2，然后1回來（花費時間1）；

第二歩：3和4過去，花費時間10，然后2回來（花費時間2）；

第三部：1和2過去，花費時間2，總耗時17。

所以貪心想法是不對的。

思路2：動態規劃。

我們先將所有人按花費時間遞增進行排序，假設前i個人過河花費的最少時間為opt[i]。

首先看初始狀態：opt[0]=0，opt[1]=T[1]， opt[2]=T[2]...

再看最后狀態：最后只可能有兩種情況

情況1：岸這邊只剩一個人。最后渡河會是1和i一起渡河。

? 狀態轉移方程：opt[i] = opt[i-1]+T[1]+T[i]

? 其中opt[i-1]是i-1個人在對岸最少時間，所以此時手電筒必定在對岸；T[1]是送手電筒回來的時間；T[i]是最后渡河時間。

情況2：岸這邊只剩兩個人。最后渡河會是1和2一起渡河。

? 狀態轉移方程：opt[i] = opt[i-2]+T[1]+T[i]+T[2]+T[2]

? 其中opt[i-2]是i-2個人在對岸最少時間，所以此時手電筒必定在對岸；T[1]是送手電筒回來的時間；T[i]是最后渡河時間（i為目前為止最后一個，所以必定比另一個人慢），第一個T[2]是送手電筒回來的時間；第二個T[2]是2和1一起渡河的時間。

這兩種最后情況其實對應的是：每個人可以選擇與1一起渡河，也可以選擇除1和2之外的一個人渡河。

那么總的狀態轉移方程取這兩者的最小值

opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] }

?

區間模型

區間模型的狀態表示一般為d[i][j]，表示區間[i, j]上的最優解，然后通過狀態轉移計算出[i+1, j]或者[i, j+1]上的最優解，逐步擴大區間的范圍，最終求得[1, len]的最優解。

【例題】給定一個長度為n（n <= 1000）的字符串A，求插入最少多少個字符使得它變成一個回文串。

?

轉載于:https://www.cnblogs.com/qionglouyuyu/p/5126573.html

總結

以上是生活随笔為你收集整理的动态规划算法的应用模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。