動态規劃套路

初識動态規劃

動态規劃的基本思想通俗來說，要想求原問題的最優解，隻需要求得子問題的最優解，組合子問題最優解，進而得到原問題的最優解。

某個問題是否能應用動态規劃，通常需要滿足 3 個條件：

最優子結構
無後續性
重複子問題

如果确認問題滿足這三個條件後，下一步就是去尋找狀态相關的決策或政策，此政策如果能在原問題上求得最優解，必然也能使用此政策，求得子問題的最優解。如果不成立，表明政策是失敗的。

什麼問題是動态規劃問題？

動态規劃問題的一般形式就是求最值；

求解動态規劃的核心問題是窮舉。

動态規劃的窮舉有點特别，因為這類問題存在「重疊子問題」，如果暴力窮舉的話效率會極其低下，是以需要「備忘錄」或者「DP

table」來優化窮舉過程，避免不必要的計算。而且，動态規劃問題一定會具備「最優子結構」，才能通過子問題的最值得到原問題的最值。

另外，雖然動态規劃的核心思想就是窮舉求最值，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，隻有列出正确的「狀态轉移方程」才能正确地窮舉。

動态規劃三要素:

重疊子問題、解決：備忘錄或者 DP table
最優子結構、注意：必須子問題是獨立的！
狀态轉移方程、

輔助你思考狀态轉移方程：

明确 base case -> 明确「狀态」-> 明确「選擇」 -> 定義 dp 數組/函數的含義。

如何列出正确的狀态轉移方程？

根據下面案例進行解釋：

根據案例：湊零錢問題–>解決最優子結構

先看下題目：給你 k 種面值的硬币，面值分别為 c1, c2 … ck，每種硬币的數量無限，再給一個總金額 amount，問你最少需要幾枚硬币湊出這個金額，如果不可能湊出，算法傳回 -1 。算法的函數簽名如下：

// coins 中是可選硬币面值，amount 是目标金額

int coinChange(int[] coins, int amount);

比如說 k = 3，面值分别為 1，2，5，總金額 amount = 11。那麼最少需要 3 枚硬币湊出，即 11 = 5 + 5 + 1。

你認為計算機應該如何解決這個問題？顯然，就是把所有可能的湊硬币方法都窮舉出來，然後找找看最少需要多少枚硬币。

1、确定 base case，這個很簡單，顯然目标金額 amount 為 0 時算法傳回 0，因為不需要任何硬币就已經湊出目标金額了。

2、确定「狀态」，也就是原問題和子問題中會變化的變量。由于硬币數量無限，硬币的面額也是題目給定的，隻有目标金額會不斷地向 base case 靠近，是以唯一的「狀态」就是目标金額 amount。

3、确定「選擇」，也就是導緻「狀态」産生變化的行為。目标金額為什麼變化呢，因為你在選擇硬币，你每選擇一枚硬币，就相當于減少了目标金額。是以說所有硬币的面值，就是你的「選擇」。

4、明确 dp 函數/數組的定義。我們這裡講的是自頂向下的解法，是以會有一個遞歸的 dp 函數，一般來說函數的參數就是狀态轉移中會變化的量，也就是上面說到的「狀态」；函數的傳回值就是題目要求我們計算的量。就本題來說，狀态隻有一個，即「目标金額」，題目要求我們計算湊出目标金額所需的最少硬币數量。

是以我們可以這樣定義 dp 函數：dp(n) 的定義：輸入一個目标金額 n，傳回湊出目标金額 n 的最少硬币數量。

實戰一、斐波那契數列–>解決重疊子問題

分析：

base case：顯然目标數值n<0 =1 =2 的時候的取值；

狀态：–

選擇： –

狀态轉移函數：目前數值為前兩個數的和

package com.learn.science.algorithm.zhijian;

import io.swagger.models.auth.In;

import java.util.HashMap;
import java.util.Map;

/**
 * @author kaka
 * @date 2021/2/7
 */
public class DPZ101fib {

    /**
     劍指 Offer 10- I. 斐波那契數列
     寫一個函數，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項（即 F(N)）。斐波那契數列的定義如下：
     F(0) = 0,   F(1) = 1
     F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     斐波那契數列由 0 和 1 開始，之後的斐波那契數就是由之前的兩數相加而得出。
     答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請傳回 1。
     示例 1：
     輸入：n = 2
     輸出：1
     示例 2：
     輸入：n = 5
     輸出：5
     提示：0 <= n <= 100

     1 1 2 3 5 8 13 ... 
     */
    // 方法一：遞歸暴力請求，效率低下（原因：大量重複計算子問題）
    public static int fib_dg(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return fib_dg(n - 1) + fib_dg(n -2);
    }
    // 方法二：帶有備忘錄的求解
    // 思想：将重複計算優化掉
    // 使用備忘錄，将結果子問題記錄，解決問題先去查是否處理過子問題，如果處理過直接拿結果，如果沒有在處理，處理完存入備忘錄；
    public static int fib_bwl(int n) {
        if (n < 1) {
            return 0;
        }
        // 備忘錄全初始化為 0
        Map<Integer, Integer> memo = new HashMap<>();
        // 進行帶備忘錄的遞歸
        return fib_bwl_dg(memo, n);
    }
    public static int fib_bwl_dg(Map<Integer, Integer> memo, int n) {
        // base case
        if (n == 1 || n == 2) {
            return 1;
        }
        // 已經計算過
        if (memo.get(n) != null) {
            return memo.get(n);
        }
        // 沒計算過計算
        int result = fib_bwl_dg(memo, n - 1) + fib_bwl_dg(memo, n - 2);
        // 存儲備忘錄
        memo.put(n, result);

        return memo.get(n);
    }
    // 方法三：dp數組的疊代解法
    // 思想：有了上面的備忘錄解法，我們可以把這個「備忘錄」獨立出來成為一張表，就叫做 DP table 吧，在這張表上完成「自底向上」的推算
    public static int fib_dp(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        // dp初始化
        Map<Integer, Integer> dp = new HashMap<>();
       // base case
        dp.put(1, 1);
        dp.put(2, 1);
        for (int i = 3; i <= n; i ++) {
            dp.put(i, dp.get(i - 1) + dp.get(i - 2));
        }
        return dp.get(n);
    }

    // 方法四：基于dp的狀态壓縮
    // 因為此題不是最值問題，不需要記錄全部狀态，隻需要記錄前兩個狀态即可；是以可以将狀态記錄的DPtable壓縮；
    public static int fid_ztys(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int per1 = 1, per2 = 1; // 前面兩個值，不需要全部的狀态值，這個隻需要記錄兩個狀态值。
        int sum = 0;
        for (int i = 3; i <= n; i ++) {
            sum = per1 + per2;
            per1 = per2;
            per2 = sum;
        }
        return sum;
    }

    public static int fib(int n) {
        int a = 0, b = 1, sum;
        for (int i = 0; i < n; i ++) {
            // sum = a + b;
            sum = (a + b)%1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(fid_ztys(10));

    }
}

實戰二、湊零錢問題–>解決最優子結構

二、湊零錢問題–>解決最優子結構

先看下題目：給你 k 種面值的硬币，面值分别為 c1, c2 … ck，每種硬币的數量無限，再給一個總金額 amount，問你最少需要幾枚硬币湊出這個金額，如果不可能湊出，算法傳回 -1 。算法的函數簽名如下：

// coins 中是可選硬币面值，amount 是目标金額

int coinChange(int[] coins, int amount);

比如說 k = 3，面值分别為 1，2，5，總金額 amount = 11。那麼最少需要 3 枚硬币湊出，即 11 = 5 + 5 + 1。

你認為計算機應該如何解決這個問題？顯然，就是把所有可能的湊硬币方法都窮舉出來，然後找找看最少需要多少枚硬币。

分析動态規劃的條件：

base case：這個很簡單，顯然目标金額 amount 為 0 時算法傳回 0，因為不需要任何硬币就已經湊出目标金額了。

狀态： amount

選擇：硬币種類，目标金額為什麼變化呢，因為你在選擇硬币，你每選擇一枚硬币，就相當于減少了目标金額。是以說所有硬币的面值，就是你的「選擇」。

狀态轉移函數：動态規劃又做自頂向下的解法，是以會有一個遞歸的 dp 函數，一般來說函數的參數就是狀态轉移中會變化的量，也就是上面說到的「狀态」；函數的傳回值就是題目要求我們計算的量。就本題來說，狀态隻有一個，即「目标金額」，題目要求我們計算湊出目标金額所需的最少硬币數量。

是以我們可以這樣定義 dp 函數：

dp(n) 的定義：輸入一個目标金額 n，傳回湊出目标金額 n 的最少硬币數量。

package com.learn.science.algorithm.zhijian;

import io.swagger.models.auth.In;

import java.util.HashMap;
import java.util.Map;

/**
 * @author kaka
 * @date 2021/2/9
 */
public class DPcoinChange {

    /**
     先看下題目：給你 k 種面值的硬币，面值分别為 c1, c2 ... ck，每種硬币的數量無限，再
     給一個總金額 amount，問你最少需要幾枚硬币湊出這個金額，如果不可能湊出，算法傳回 -1 。
     算法的函數簽名如下：
     // coins 中是可選硬币面值，amount 是目标金額
     int coinChange(int[] coins, int amount);
     比如說 k = 3，面值分别為 1，2，5，總金額 amount = 11。那麼最少需要 3 枚硬币湊出，即 11 = 5 + 5 + 1。
     你認為計算機應該如何解決這個問題？顯然，就是把所有可能的湊硬币方法都窮舉出來，然後找找看最少需要多少枚硬币。

     1，暴力遞歸
        最優子結構，子問題必須互相獨立；
     原問題：要考總分最高分；
     子問題：每一門課都考最高分，國文，資料，英語都考最高。  子問題不互相影響，考國文不會影響我資料和英語的分數；
     原問題：給定金額找出用最少多少枚硬币；
     子問題，米格
     */
    /**
    // coins 中是可選硬币面值：List[int]= 1 2 5 三種面值的硬币
    // amount 是目标金額：int amount=11 總金額
    // 僞碼架構
    int coinChange(int[] coins, int amount) {
        // 定義湊出金額n，至少要dp(n)個硬币
        def dn(n) {
            // 做選擇，選擇需要硬币最少的那個結果
            for (int coin : coins) {
                res = min(res, 1 + dp(n - coin));
                return res;
            }
        }
        // 題目要求的最終結果是 dp(amount)
        return dp(amout);
    }
    */
    /**
     如何列出正确的狀态轉移方程？
     1、确定 base case，這個很簡單，顯然目标金額 amount 為 0 時算法傳回 0，因為不需要任何硬币就已經湊出目标金額了。
     2、确定「狀态」，也就是原問題和子問題中會變化的變量。由于硬币數量無限，硬币的面額也是題目給定的，隻有目标金額會不斷地向 base case 靠近，是以唯一的「狀态」就是目标金額 amount。
     3、确定「選擇」，也就是導緻「狀态」産生變化的行為。目标金額為什麼變化呢，因為你在選擇硬币，你每選擇一枚硬币，就相當于減少了目标金額。是以說所有硬币的面值，就是你的「選擇」。
     4、明确 dp 函數/數組的定義。我們這裡講的是自頂向下的解法，是以會有一個遞歸的 dp 函數，一般來說函數的參數就是狀态轉移中會變化的量，也就是上面說到的「狀态」；函數的傳回值就是題目要求我們計算的量。就本題來說，狀态隻有一個，即「目标金額」，題目要求我們計算湊出目标金額所需的最少硬币數量。
     // 是以我們可以這樣定義 dp 函數：!!!!!!!!!!!! 最難的是找到狀态轉移函數
     // dp(n) 的定義：輸入一個目标金額 n，傳回湊出目标金額 n 的最少硬币數量。
     */
    // 方法一：暴力遞歸
    public static int coinChange_dg(int[] coins, int amount) {
        // base case
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        // 狀态：amount
        // 選擇：選擇硬币，導緻狀态變化
        int cnums = Integer.MAX_VALUE; // 求最小值，設定為無窮大
        for (int coin : coins) {
            // 子問題選擇硬币
            int subproblem = coinChange_dg(coins, amount - coin);
            // 子問題無解跳過
            if (subproblem == -1) {
                continue;
            }
            // 有解看哪個小
            cnums = Math.min(cnums, subproblem + 1);
        }
        if (cnums == Integer.MAX_VALUE) {
            cnums = -1;
        }
        return cnums;
    }

    // 方法二：帶有備忘錄的求解
    // 思想：将重複計算優化掉
    // 使用備忘錄，将結果子問題記錄，解決問題先去查是否處理過子問題，如果處理過直接拿結果，如果沒有在處理，處理完存入備忘錄；
    public static int coinChange_bwl(int[] coins, int amount) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        // 初始化備忘錄 : key:狀态金額，value:硬币數
        Map<Integer, Integer> map = new HashMap<>();
        // 找最小硬币數
        return coinChange_bwl_dg(coins, amount, map);
    }
    public static int coinChange_bwl_dg(int[] coins, int amount, Map<Integer, Integer> map) {
        // base case
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        // 備忘錄查找
        if (map.get(amount) != null) {
            return map.get(amount);
        }
        int cnums = Integer.MAX_VALUE;
        // 沒有，進行選擇計算
        for (int coin : coins) {
            // 子問題
            int sub_num = coinChange_bwl_dg(coins, amount - coin, map);
            // 無解
            if (sub_num == -1) {
                continue;
            }
            cnums = Math.min(cnums, sub_num + 1);
        }
        // 記錄備忘錄
        map.put(amount, cnums == Integer.MAX_VALUE ? -1 : cnums);

        return coinChange_bwl_dg(coins, amount, map);
    }

    // 方法三：dp數組的疊代解法
    // 思想：有了上面的備忘錄解法，我們可以把這個「備忘錄」獨立出來成為一張表，就叫做 DP table 吧，在這張表上完成「自底向上」的推算
    public static int coinChange_dp(int[] coins, int amount) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        // 定義dp數組
        Map<Integer, Integer> map = new HashMap<>();
        return coinChange_dp_dg(coins, amount, map);
    }
    public static int coinChange_dp_dg(int[] coins, int amount, Map<Integer, Integer> map) {
        // base case
        map.put(0, 0);
        // 外層 for 循環在周遊所有狀态的所有取值
        for (int i = 1; i <= amount; i ++) {
            // 内層 for 循環在求是所有選擇的最小值
            for (int coin : coins) {
                // 子問題無解，跳過
                if (i - coin < 0) {
                    continue;
                }
                // 子問題解
                int sub_num = coinChange_dp_dg(coins, i - coin, map);
                sub_num = map.get(i) == null ? sub_num + 1 : Math.min(map.get(i), sub_num + 1);
                // 存儲dp
                map.put(i, sub_num);
            }
        }
        return map.get(amount) == null ? -1 : map.get(amount);
    }

    public static void main(String[] args) {
        System.out.println(coinChange_dg(new int[]{1,2,5}, 11));
        System.out.println(coinChange_bwl(new int[]{1,2,5}, 11));
        System.out.println(coinChange_dp(new int[]{1,2,5}, 11));

    }

}

讀書筆記，學習筆記。

動态規劃套路

初識動态規劃

什麼問題是動态規劃問題？

輔助你思考狀态轉移方程：

如何列出正确的狀态轉移方程？

實戰一、斐波那契數列–>解決重疊子問題

實戰二、湊零錢問題–>解決最優子結構

繼續閱讀

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

LeetCode OJ Binary Tree Right Side View

Effective Java 8:通用程式設計

leetcode809

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希