動態規劃演算法與分治演算法差別

⑴ 【演算法】請問動態規劃和分治策略的差別是不是就在於對子問題的處理方式上

動態規劃與分治策略都是將一個問題分解成為若乾子問題，動態規劃和分治相比，則有一個非常有用的性質，就是 動態規劃中使用的子問題有大部分都是相同的（重疊子問題），這樣我就可以通過記錄每個子問題的答案使得 每個子問題 不被重復計算，從而 做到了 時間復雜度 上的 本質優化。
但是有些問題本身的子問題就不怎麼重復，那樣的話其實用不用動態規劃都是一樣的。

⑵ 動態規劃演算法的基本思想

動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。

拓展資料：

動態規劃的實質是分治思想和解決冗餘，因此動態規劃是一種將問題實例分析為更小的、相似的子問題，並存儲子問題的解而避免計算重復的子問題，以解決最優化問題的演算法策略
動態規劃所針對的問題有一個顯著的特徵，即它對應的子問題樹中的子問題呈現大量的重復。動態規劃的關鍵在於，對於重復的子問題，只在第一次遇到時求解，並把答案保存起來，讓以後再遇到時直接引用，不必要重新求解。

⑶ 演算法策略的演算法策略間的關系

1、對問題進行分解的演算法策略——分治法與動態規劃法
共同點：（1）分治法與動態規劃法實際上都是遞歸思想的運用
（2）二者的根本策略都是對問題進行分解，找到大規模與小規模的關系，然後通過解小規模的解，得出大規模的解
不同點： 適用於分治法的問題分解成子問題後，各子問題間無公共子子問題，而動態規劃法相反。
動態規劃法 = 分治演算法思想 + 解決子問題間的冗餘情況
2、多階段逐步解決問題的策略——貪心演算法和動態規劃法
貪心演算法：每一步都根據策略得到一個結果，並傳遞到下一步，自頂向下，一步一步地做出貪心決策。
動態規劃演算法：每一步決策得到的不是一個唯一結果，而是一組中間結果（且這些結果在以後各步可能得到多次引用），只是每一步都使問題的規模逐步縮小，最終得到問題的一個結果。

⑷ 動態規劃和貪心演算法的區別

動態規劃和貪心演算法的區別

1、動態規劃演算法中，每步所做的選擇往往依賴於相關子問題的解，因而只有在解出相關子問題時才能做出選擇。而貪心演算法，僅在當前狀態下做出最好選擇，即局部最優選擇，然後再去解做出這個選擇後產生的相應的子問題。

2、動態規劃演算法通常以自底向上的方式解各子問題，而貪心演算法則通常自頂向下的方式進行。

⑸ 簡述貪心，遞歸，動態規劃，及分治演算法之間的區別和聯系

聯系：都是問題求解之時的一種演算法。

區別：

一、作用不同

1、貪心演算法：把子問題的解局部最優解合成原來解問題的一個解。

2、遞歸演算法：問題解法按遞歸演算法實現。如Hanoi問題；數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。

3、動態規劃：動態規劃演算法通常用於求解具有某種最優性質的問題。

4、分治演算法：可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。

二、方法不同

1、貪心演算法：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，演算法得到的是在某種意義上的局部最優解。

2、遞歸演算法：通過重復將問題分解為同類的子問題而解決問題。

3、動態規劃：將過程分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。

4、分治演算法：將一個規模為N的問題分解為K個規模較小的子問題。

三、特點不同

1、貪心演算法：根據題意選取一種量度標准。

2、遞歸演算法：遞歸就是在過程或函數里調用自身。

3、動態規劃：雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。

4、分治演算法：原問題可以分解為多個子問題；原問題在分解過程中，遞歸地求解子問題；在求解並得到各個子問題的解後。

⑹ 比較「分治法」和「動態規劃法」的異同點和優缺點

共同點：
將待求解的問題分解成若乾子問題，先求解子問題，然後再從這些子問題的解得到原問題的解。
不同點：
1、適合於用動態規劃法求解的問題，分解得到的各子問題往往不是相互獨立的；
而分治法中子問題相互獨立。
2、動態規劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復雜度，效率較高；
而分治法中對於每次出現的子問題均求解，導致同樣的子問題被反復求解，故產生指數增長的時間復雜度，效率較低。

⑺ 動態規劃演算法的分段每一段必須是相同的嗎

是的，動態規劃演算法的分段每一段必須是相同的是的每一段必須是相同的因為動態規則的演算法他是這樣設置的我們在每一個分段它的一個數值呢必須是相同所以他的每一段的動態規則賦值呢是一樣的所以他每一段必須是相同的這是他規劃演算法的是的每一段必須是相同的

⑻ 動態規劃

動態規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解 決策過程最優化 的過程。20世紀50年代初，美國數學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優化問題時，提出了著名的最優化原理，從而創立了動態規劃。動態規劃的應用極其廣泛，包括工程技術、經濟、工業生產、軍事以及自動化控制等領域，並在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統可靠性問題等中取得了顯著的效果。

雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如 線性規劃、非線性規劃 )，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。

在現實生活中，有一類活動的過程，由於它的特殊性，可將過程分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定， 它依賴於當前面臨的狀態，又影響以後的發展 。當各個階段決策確定後，就組成一個決策序列，因而也就確定了整個過程的一條活動路線．這種把一個問題看作是一個 前後關聯具有鏈狀結構的多階段過程 就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的， 決策依賴於當前狀態，又隨即引起狀態的轉移 ，一個決策序列就是在變化的狀態中產生出來的，故有「動態」的含義，稱這種解決多階段決策最優化的過程為動態規劃方法

動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。 動態規劃演算法與分治法類似 ，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是， 適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的 。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃演算法多種多樣，但它們具有相同的填表格式。

以一個例子來說明動態規劃的概念(leetcode第5題最長迴文子串)：

在這個例子中，一個字元串如果是迴文子串，那麼去掉頭尾也照樣是迴文子串。而每一個字元都有可能是最長迴文子串的一部分。

上面這個例子使用一個二維數組表示各個階段的狀態，這個二維數組的行是子串的起始位置，列是子串的結束位置。由於j>=i，所以只需要考慮二維數組的主對角線的上半部分，對角線上的值永遠是true。用true表示這個子串是迴文串，false不是迴文串。那麼對於某個固定位置的數組元素來說，它的值依賴於左下角的元素的值。進行填充的時候只能一列一列地進行填充，同一列的元素從上到下依次填充。

⑼ 遞歸，分治演算法，動態規劃和貪心選擇的區別

遞歸，簡單的重復，計算量大。 分治，解決問題獨立，分開計算，如其名。 動態規劃演算法通常以自底向上的方式解各子問題， 貪心演算法則通常以自頂向下的方式進行； 動態規劃能求出問題的最優解，貪心不能保證求出問題的最優解