請問動態規劃和滑動視窗的區別是什麼？

1樓：Johngo學長

emmm...貌似完全不同

可能有些問題用到了動態規劃解決，但同時利用了滑動視窗的方法。

下面是之前寫過的兩篇，可以嘗試看下

Johngo學長：學妹上岸位元組的「動態規劃」寶典Johngo學長：【完虐演算法系列】「字串 – 滑動視窗」覆盤總結很清晰的兩篇文章，應該可以幫助你完全解決你迷茫的地方。

2樓：

滑動視窗是一種資料結構，用來實現動態規劃的思想：

第n次充分利用過去 n-1次決策的資訊（本例是利用第 n-1 次）

以無重複字元的最長子串為例

可以直接蠻輪，但下次蠻輪的起點設定為上次蠻輪的重點，減少重複計算

3樓：

動態規劃準確說是一種解決問題的思路：把大的問題化解為多個小型問題的組合。你舉例的這幾個題裡，恰好滑動視窗的方式是具體實現動態規劃的方式，所以它們的關係就是通用思想和具體問題實現的關係。

動態規劃-鋼條切割問題 - RunningSnail - 部落格園這個就不是滑動視窗，還有一些二維問題也可以用動態規劃。

在我的理解裡，動態規劃是把不同級別問題的解直接聯絡起來了。N階問題--->N階的解；N-1階問題--->N-1階的解；然後 N階的解是直接從 N-1階的解直接得過來，也有把N-1階，N-2階，N-3階.....等多個小級別問題的解組合得到N階的解。

這個就是通用思路，在鋼條切割問題裡是看得比較明顯的。

4樓：守夜人

滑動視窗屬於動態規劃的一種。

動態規劃的實質是多階段決策問題，如果一類活動過程可以分為若干個互相聯絡的階段，在每乙個階段都需作出決策（採取措施），乙個階段的決策確定以後，常常影響到下乙個階段的決策，從而就完全確定了乙個過程的活動路線，則稱它為多階段決策問題。