從本篇開始，我們就正式開始進(jìn)入 動態(tài)規(guī)劃 系列文章的學(xué)習(xí)。

本文先來練習(xí)兩道通過 建立緩存表 優(yōu)化解題過程的題目，對如何將 遞歸函數(shù) 修改成 動態(tài)規(guī)劃 的流程有個基本的熟悉。

基本流程

1. 用最簡單的想法完成題目要求的 遞歸 函數(shù)；

• 定義明確 遞歸函數(shù) 的功能?。?！

2. 分析是否存在 重疊子問題 ，即能否進(jìn)行 剪枝 操作；

3. 建立 數(shù)組或集合 緩存，尋找 狀態(tài)轉(zhuǎn)移方程 ，完成動態(tài)規(guī)劃。

不太懂沒關(guān)系，相信通過下面兩道題目的練習(xí)就能找到感覺。

走到目標(biāo)位置

假設(shè)有 N 個位置從左到右排成一排，記為 1 ~ N 。一個機(jī)器人開始在 start 位置上（1 ≤ start ≤ N），可以往左或者往右走，規(guī)定機(jī)器人只能走 K 步，最終能來到 aim（1 ≤ aim ≤ N） 位置的方法有多少種。

注意：

• 若機(jī)器人在 1 位置，下一步只能向右走到 2 位置；

• 若機(jī)器人在 N 位置，下一步只能向左走到 N-1 位置。

遞歸的準(zhǔn)備

定義遞歸函數(shù)的功能： 從當(dāng)前位置出發(fā)，走 k 步到達(dá)目的地，共有多少種行走的方法。

思考遞歸需要的參數(shù)： 當(dāng)前位置、目標(biāo)位置、需要走的步數(shù)、能行走的范圍。

明確遞歸的邊界條件： 如果當(dāng)前需要走的步數(shù)為 0 ，且此時正好在目標(biāo)位置，即找到了一種有效的行走方法；反之沒有找到。

思路

尋找相同類型子問題：

• 若機(jī)器人當(dāng)前在 1 號位置 ，只能 往右走 ，因此走 k 步的答案，應(yīng)該和在 2 號位置上走 k-1 步的答案一樣。
• 若機(jī)器人當(dāng)前在 N 號位置 ，只能 往左走 ，因此走 k 步的答案，應(yīng)該和在 N-1 號位置上走 k-1 步的答案一樣。
• 若機(jī)器人當(dāng)前在 中間位置 ，因此走 k 步的答案，應(yīng)該是前一個位置走 k-1 步與后一個位置走 k-1 步的總和。

代碼

public static int ways(int start, int K, int aim, int N) {
    if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        return -1;
    }
    // 調(diào)用遞歸函數(shù)
    return process(start, K, aim, N);
}

private static int process(int cur, int remain, int aim, int N) {
    // 已經(jīng)來到目標(biāo)位置，且步數(shù)為 0。
    if (remain == 0) {
        return cur == aim ? 1 : 0;
    }
    // 到了最左邊
    if (cur == 1) {
        return process(2, remain - 1, aim, N);
    }
    // 到了最右邊
    if (cur == N) {
        return process(N - 1, remain - 1, aim, N);
    }
    // 在中間位置
    return process(cur - 1, remain - 1, aim, N) + process(cur + 1, remain - 1, aim, N);
}

相信上面的代碼很容易看懂 ~

思考上面的遞歸過程，畫出部分遞歸調(diào)用的過程圖：

例如，當(dāng)前機(jī)器人位置在 4 號位置還有 5 步要走，用 4,5 表示。

1. 若往左走，來到 3 號位置，還有 4 步要走，用 3,4 表示；
2. 若往右走，來到 5 號位置，還有 4 步要走，用 5,4 表示；

以此類推，遞歸調(diào)用圖中出現(xiàn)了相同的 4,3 ，即出現(xiàn)了 重疊子問題 ，因此就有必要進(jìn)行 緩存優(yōu)化 。

接下來我們使用 緩存 的方法優(yōu)化該遞歸過程:

思路

寫完遞歸的代碼之后，再來修改緩存代碼就變的非常簡單。

考慮到遞歸傳遞的參數(shù)中 process(int cur, int remain, int aim, int N) ，只有 cur, remain 兩個參數(shù)會發(fā)生變化，因此，就可以構(gòu)造一個 以這兩個參數(shù)為變量 的 二維 dp 數(shù)組 。

• 1. 思考兩個變量的取值范圍，構(gòu)造數(shù)組長度。由于1 ≤ cur ≤ N ,0 ≤ remain ≤ K ，因此將數(shù)組長度設(shè)置為 dp[N+1][K+1] 。
• 2. 將 dp 數(shù)組值設(shè)置為 -1。若計算過該位置該步長的情況，就更新 dp 中對應(yīng)位置的值。因此，若值不為 -1 ，說明之前計算過，可以直接獲取，達(dá)到了剪枝的目的。
• 3. 更新的方法是，先用變量 ans 記錄下情況數(shù)，在退出本層遞歸時更新 dp 表。

緩存優(yōu)化代碼

// dp緩存法
public static int ways(int start, int K, int aim, int N) {
    if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        return -1;
    }
    int[][] dp = new int[N + 1][K + 1];
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            dp[i][j] = -1;
        }
    }
    return process(start, K, aim, N, dp);
}

private static int process(int cur, int remain, int aim, int N, int[][] dp) {
    if (dp[cur][remain] != -1) {
        return dp[cur][remain];
    }
    int ans = 0;
    if (remain == 0) {
        ans = cur == aim ? 1 : 0;
    } else if (cur == 1) {
        ans = process(2, remain - 1, aim, N, dp);
    } else if (cur == N) {
        ans = process(N - 1, remain - 1, aim, N, dp);
    } else {
        ans = process(cur - 1, remain - 1, aim, N, dp) + process(cur + 1, remain - 1, aim, N, dp);
    }
    dp[cur][remain] = ans;
    return ans;
}

看懂思路之后，上面的代碼也很容易看懂！

因為該遞歸是從原始問題開始，逐步分解為子問題的，因此稱為 自頂向下 的 備忘錄 遞歸解法。

優(yōu)化后的代碼雖然使用 dp 數(shù)組進(jìn)行了一定量的 剪枝 操作，但這并不是最終 動態(tài)規(guī)劃版本 的代碼，接下來，我們通過畫圖來尋找真正的 狀態(tài)轉(zhuǎn)移方程:

假設(shè) N = 8，步數(shù) K = 5，起始位置 start = 6，目標(biāo)位置 aim = 3。由此可以畫出初始 dp 表為：（坐標(biāo) 用( 位置 , 剩余步數(shù) )表示；表中的 數(shù)字大小 表示到達(dá)目標(biāo)位置的 方法數(shù) ）

紅色代表初始位置 (6,5)，藍(lán)色代表最終目標(biāo)位置 (3,0)。
沒有 0 號位置，因此第 0 列無效，用 × 表示。

根據(jù)遞歸函數(shù)中代碼邏輯發(fā)現(xiàn)：

1. 當(dāng)步數(shù)為 0 時，只有目標(biāo)位置的值為 1 ，其余均為 0。

    // 已經(jīng)來到目標(biāo)位置，且步數(shù)為 0。
    if (remain == 0) {
        return cur == aim ? 1 : 0;
    }

2. 當(dāng)當(dāng)前位置 cur 為 1 時，依賴 2 號位置，步數(shù)小 1 的信息（向左下依賴）。當(dāng)當(dāng)前位置 cur 為 N 時，依賴 N - 1 號位置，步數(shù)小 1 的信息（向左上依賴）。

    // 到了最左邊
    if (cur == 1) {
        return process(2, remain - 1, aim, N);
    }
    // 到了最右邊
    if (cur == N) {
        return process(N - 1, remain - 1, aim, N);
    }

3. 當(dāng)在中間位置時，共同依賴前后一個位置，步數(shù)均小 1 的信息（向左上和左下依賴）。

    // 在中間位置
    return process(cur - 1, remain - 1, aim, N) + process(cur + 1, remain - 1, aim, N);

由此可以在圖中標(biāo)注依賴關(guān)系方向。

根據(jù)圖中的依賴方向很容易一行一行的填出所有答案：

表中坐標(biāo) (6,5) 的值是 5 ，說明初始在位置 6 走 5 步，走到位置 3 共有 5 種走法。

這張表就是動態(tài)規(guī)劃表！

現(xiàn)在我們就通過代碼模擬剛才的填表過程：

// 動態(tài)規(guī)劃
public static int ways3(int start, int K, int aim, int N) {
    if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        return -1;
    }
    int[][] dp = new int[N + 1][K + 1];
    dp[aim][0] = 1;
    for (int remain = 1; remain <= K; remain++) {
        dp[1][remain] = dp[2][remain - 1];
        for (int cur = 2; cur < N; cur++) {
            dp[cur][remain] = dp[cur - 1][remain - 1] + dp[cur + 1][remain - 1];
        }
        dp[N][remain] = dp[N - 1][remain - 1];
    }
    return dp[start][K];
}

代碼解釋

第一列只有dp[aim][0]位置為 1 ，其余位置均為 0 。之后從上往下從左到右，一列一列的填寫：

• for 循環(huán)中，把第一行和最后一行單獨填寫，即分別向左下和左上依賴。中間行分別依賴左上和左下部分的值。
• 最終返回要求的目標(biāo)位置的 dp[start][K] 的值。

因為該方法是從最小的子問題開始逐步求解，因此稱為 自底向上的動態(tài)規(guī)劃。

上面這道題使用了 一張 dp 表 完成了自底向上的動態(tài)規(guī)劃，下面我們增加點難度，來看一道使用 兩張 dp 表 才能完成的動態(tài)規(guī)劃題目。

紙牌博弈問題

?？途W(wǎng)鏈接-紙牌博弈問題：給定一個整型數(shù)組arr，代表數(shù)值不同的紙牌排成一條線。玩家 A 、B依次拿走每張紙牌，規(guī)定玩家 A 先拿，玩家 B 后拿，每個玩家每次只能拿走最左和最右側(cè)的紙牌，玩家A和玩家B絕頂聰明。請返回最后的獲勝者的分?jǐn)?shù)。

例如：
返回獲勝者的答案應(yīng)該是：1+100=101

遞歸的準(zhǔn)備

定義遞歸函數(shù)的功能：

1. 如果是 先手 則能夠獲得的最大值；
2. 如果是 后手 則能夠獲得的最大值。

思考遞歸需要的參數(shù)： 當(dāng)前剩余的整個數(shù)組、兩個邊界 L 和 R 。

明確遞歸的邊界條件： 只剩下一張牌時，如果是先手，獲得該牌的數(shù)值，如果是后手，獲得數(shù)值為 0 。

思路

1. 如果是先手：

• 拿了左側(cè) L ，最終獲得的分?jǐn)?shù) = 此時左側(cè) L 的分?jǐn)?shù) + 剩下的部分做為后手時拿到的分?jǐn)?shù)。
• 拿了右側(cè) R ，最終獲得的分?jǐn)?shù) = 此時右側(cè) R 的分?jǐn)?shù) + 剩下的部分做為后手時拿到的分?jǐn)?shù)。
• 此時應(yīng)該取兩種情況的 最大值 作為最終的抉擇。

2. 如果是后手：

• 此時 [L, R] 上的抉擇權(quán)就不在自己手中了（因為此時先手得先拿）。
• 因此，作為后手的自己只能獲得先手拿過之后的最小值（先手肯定不會讓你拿最大了！又不傻~）

代碼

public static int win(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int first = f(arr, 0, arr.length - 1);
    int after = g(arr, 0, arr.length - 1);
    return Math.max(first, after);
}
// 先手
private static int f(int[] arr, int L, int R) {
    if (L == R) {
        return arr[L];
    }
    // 先手拿左側(cè)牌獲得的分?jǐn)?shù)
    int p1 = arr[L] + g(arr, L + 1, R);
    // 先手拿右側(cè)牌獲得的分?jǐn)?shù)
    int p2 = arr[R] + g(arr, L, R - 1);
    return Math.max(p1, p2);
}
// 后手
private static int g(int[] arr, int L, int R) {
    if (L == R) {
        return 0;
    }
    // 如果先手拿了左側(cè)牌，后手獲得的分?jǐn)?shù)
    int p1 = f(arr, L + 1, R);
    // 如果先手拿了右側(cè)牌，后手獲得的分?jǐn)?shù)
    int p2 = f(arr, L, R - 1);
    return Math.min(p1, p2);
}

思考上面的遞歸過程，畫出部分遞歸調(diào)用的過程圖：

例如，此時紙牌長度下標(biāo)為 1~5，用 1,5 表示。

1. 若拿左側(cè)，還剩下 2~5，用 2,5 表示；
2. 若拿右側(cè)，還剩下 1~4，用 1,4 表示；

以此類推，遞歸調(diào)用圖中出現(xiàn)了相同的 2,4 ，即出現(xiàn)了 重疊子問題 ，因此就有必要進(jìn)行 緩存優(yōu)化 。

這次我們直接根據(jù)該遞歸函數(shù)畫出最終版本的 動態(tài)規(guī)劃 dp 表。

思路

考慮到遞歸傳遞的參數(shù)中 f(int[] arr, int L, int R) ，只有 L, R 兩個參數(shù)會發(fā)生變化，且 f 和 g 函數(shù)相互依賴。因此，可以構(gòu)造 兩個 以這兩個參數(shù)為變量 的 二維 dp 數(shù)組 。

• 1. 思考兩個變量的取值范圍，構(gòu)造數(shù)組長度。由于0 ≤ L ≤ R ＜ N，因此將數(shù)組長度均設(shè)置為 dp[N][N] 。
• 2. 由于 L ≤ R ， dp 表為上三角矩陣。

假設(shè)，數(shù)組 arr={1, 2, 100, 4}。

根據(jù)遞歸函數(shù)中代碼邏輯發(fā)現(xiàn)：

1. 當(dāng)為先手時，fmap 的值為：

• L == R 時為當(dāng)前 arr[L] 的值。
• L != R 時依賴 gmap 表對應(yīng)相同位置中 arr[L] + gmap(L + 1, R) 與 arr[R] + gmap(L , R - 1) 中的最大值。

這里一定要區(qū)分好誰和誰相加后取最大值哦~位置關(guān)系別搞亂了！

private static int f(int[] arr, int L, int R) {
    if (L == R) {
        return arr[L];
    }
    // 先手拿左側(cè)牌獲得的分?jǐn)?shù)
    int p1 = arr[L] + g(arr, L + 1, R);
    // 先手拿右側(cè)牌獲得的分?jǐn)?shù)
    int p2 = arr[R] + g(arr, L, R - 1);
    return Math.max(p1, p2);
}

2. 當(dāng)為后手時，gmap 的值為：

• L == R 時為 0 。
• L != R 時依賴 fmap 表對應(yīng)相同位置中 (L + 1, R) 與 (L , R - 1) 中的最小值。

private static int g(int[] arr, int L, int R) {
    if (L == R) {
        return 0;
    }
    // 如果先手拿了左側(cè)牌，后手獲得的分?jǐn)?shù)
    int p1 = f(arr, L + 1, R);
    // 如果先手拿了右側(cè)牌，后手獲得的分?jǐn)?shù)
    int p2 = f(arr, L, R - 1);
    return Math.min(p1, p2);
}

由此可以在圖中展示出依賴關(guān)系：

由此可以完整填出整個 fmap 和 gmap 表：

因此，返回最大值 max(101,6) = 101。

這兩張表就是最終動態(tài)規(guī)劃表！

現(xiàn)在我們就通過代碼模擬剛才的填表過程：

public static int win(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] fmap = new int[N][N];
    int[][] gmap = new int[N][N];
    for (int i = 0; i < N; i++) {
        fmap[i][i] = arr[i];
        // new 數(shù)組時， gmap 本來就為 0
        // gmap[i][j] = 0;
    }
    for (int startCol = 1; startCol < N; startCol++) {
        int L = 0;
        int R = startCol;
        // 從左上到右下斜著填表
        while (R < N) { // R 比 L 先到達(dá)邊界
            fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
            gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
            // 斜向下走
            L++;
            R++;
        }
    }
    return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
}

擴(kuò)展

由于本題的 dp 表是兩張 上三角矩陣，因此可以采用 壓縮空間 的辦法，將 二維數(shù)組 矩陣 壓縮 為 一維數(shù)組 ，可以減少大約一半的矩陣空間，但空間復(fù)雜度仍然是 $O(N^2)$ 級別的。

這里涉及到了有關(guān) 矩陣壓縮 的知識，有興趣的小伙伴可以自行學(xué)習(xí)下 如何將三角矩陣壓縮成為一維數(shù)組 哦！

~ 點贊 ~ 關(guān)注 ~ 不迷路 ~！??！文章來源地址http://www.zghlxwxcb.cn/news/detail-833648.html

到了這里，關(guān)于【算法 - 動態(tài)規(guī)劃】原來寫出動態(tài)規(guī)劃如此簡單！的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！