基礎算法之-動態規劃

2020 年 10 月 29 日
筆記
JAVA, 算法, 算法/algorithm

動態規劃是一種算法技巧，基本思想是：如果一個問題的解，可以拆分成重複多個步驟的子問題,解決當前的問題後，到達一種狀態，後一個子問題的求解是建立在現有狀態的基礎上，最後在每個子問題的最優解的基礎上，得出整體的最優解。

《數據結構與算法-Java》這本書提到，動態規劃是將遞歸算法改寫為非遞歸算法，把非遞歸的子問題答案記錄到一個表內，這種技巧叫動態規劃。

基本思想

若要解一個給定問題，我們需要解其不同部分（即子問題），再合併子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用

特點

最優化原理（最優子結構性質）
最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。
無後效性
將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無後向性，又稱為無後效性。
子問題的重疊性
動態規划算法的關鍵在於解決冗餘，這是動態規划算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間複雜度要大於其他的算法。選擇動態規划算法是因為動態規划算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間 [8] 。

分治與動態規劃

共同點：二者都要求原問題具有最優子結構性質,都是將原問題分而治之,分解成若干個規模較小(小到很容易解決的程序)的子問題.然後將子問題的解合併,形成原問題的解.
不同點：分治法將分解後的子問題看成相互獨立的，通過用遞歸來做。動態規劃將分解後的子問題理解為相互間有聯繫,有重疊部分，需要記憶，通常用迭代來做。

步驟

分析優化解的結構
遞歸地定義最優解的代價
自底向上地計算優化解的代價保存之，並獲取構造最優解的信息
根據構造最優解的信息構造優化解

典型問題

1. 斐波那契數列

斐波那契數列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n – 1)+F(n – 2)（n ≥ 3，n ∈ N*）即：0、1、1、2、3、5、8、13、21、34、……

1. 問題分解

當n>2時，依賴n-1的結果和n-2的結果
n-1的結果依賴n-2和n-3的記過。
遞歸過程會重複調用f(n-2) 2 次

狀態轉移方程

遞歸：

f(n)= f(n-1）+ f(n-2)
循環：

 for (int i = 2; i <= N; i++) {
      cache[i] = cache[i-1] + cache[i-2];
  }

2. 01背包類問題

轉自：198. 打家劫舍
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你不觸動警報裝置的情況下，一夜之內能夠偷竊到的最高金額。

分解：

第i家的被打劫，要求第i-1家不被打劫，第i-2家及以前的無關
到第i家打劫的結果最大化利益，前i-1家的金額與前i-2家的金額 + 第i家的金額比較，取較大的一個

狀態轉移方程

dp[i]= max(dp[i-2]+i,dp[i-1]);

實現：

public int massage3(int[] nums) {
       if (nums == null || nums.length == 0) {
        return 0;
    }
    int length = nums.length;
    if (length == 1) {
        return nums[0];
    }
    int[] dp = new int[length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[length - 1];
}

簡單總結

動態規劃的問題基本都是遞歸可以解決的，用空間換時間，用一個表來記錄歷史完成的結果狀態，減少遞歸的次數。

參考

//www.cnblogs.com/raichen/p/5772056.html
//blog.csdn.net/ailaojie/article/details/83014821
//www.cnblogs.com/hithongming/p/9229871.html

Tags: JAVA 算法算法/algorithm