我們前面看過了0-1背包問題，矩陣最短路徑長(zhǎng)度問題和萊文斯坦最短 編輯距離問題。

在三個(gè)問題的狀態(tài)樹中。
0-1背包問題：用(i,cw)表示狀態(tài)。i 表示要將要處理第i個(gè)物品，cw表示當(dāng)前總重量。因?yàn)?i,cw)有重復(fù)的，所以使用動(dòng)態(tài)規(guī)劃。

矩陣最短路徑長(zhǎng)度：用(i,j,currentPathSum)表示狀態(tài)。表示當(dāng)前將要處理第i行第j列的數(shù)據(jù)，在處理之前已經(jīng)走過的路徑長(zhǎng)度是currentPathSum。因?yàn)樵?i,j)狀態(tài)下有不同的currentPathSum，我們只需要留下最小的currentPathSum即可。

萊文斯坦問題：用(i,j,edist)表示狀態(tài)，i表示指針在a字符串的位置，j表示指針在b字符串的位置，(i,j)都表示將要處理的字符位置，edist表示到達(dá)(i,j)時(shí)已經(jīng)執(zhí)行的編輯次數(shù)。因?yàn)樵?i,j)狀態(tài)下有不同的edist，我們只需要留下最小的edist即可。

矩陣最短路徑長(zhǎng)度的目標(biāo)是要找到最小的長(zhǎng)度，所以在每個(gè)狀態(tài)只保留最小的長(zhǎng)度。
萊文斯坦問題的目標(biāo)是要找到最小的編輯距離，所以在每個(gè)狀態(tài)只保留最小的編輯距離。
0-1背包問題目標(biāo)是求最大的重量，為什么不只保留最大的重量就可以呢？因?yàn)?-1背包問題的限制條件也是重量。它要求總重量不能超過w。所以每一步?jīng)Q策之后的重量都有可能是一個(gè)結(jié)果。所以不能剪裁，需要保留。

總結(jié)

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

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