base case和備忘錄初始值怎么定？

很多讀者對(duì)動(dòng)態(tài)規(guī)劃問題的 base case、備忘錄初始值等問題存在疑問。

本文就專門講一講這類問題，順便聊一聊怎么通過題目的蛛絲馬跡揣測(cè)出題人的小心思，輔助我們解題。

看下力扣第 931 題「下降路徑最小和」，輸入為一個(gè)n * n的二維數(shù)組matrix，請(qǐng)你計(jì)算從第一行落到最后一行，經(jīng)過的路徑和最小為多少。

函數(shù)簽名如下：

int minFallingPathSum(int[][] matrix);

就是說你可以站在matrix的第一行的任意一個(gè)元素，需要下降到最后一行。

每次下降，可以向下、向左下、向右下三個(gè)方向移動(dòng)一格。也就是說，可以從matrix[i][j]降到matrix[i+1][j]或matrix[i+1][j-1]或matrix[i+1][j+1]三個(gè)位置。

請(qǐng)你計(jì)算下降的「最小路徑和」，比如說題目給了一個(gè)例子：

今天這道題也是類似的，不算是困難的題目，所以 我們借這道題來講講 base case 的返回值、備忘錄的初始值、索引越界情況的返回值如何確定 。

不過還是要通過 動(dòng)態(tài)規(guī)劃的標(biāo)準(zhǔn)套路介紹一下這道題的解題思路，首先我們可以定義一個(gè)dp數(shù)組：

int dp(int[][] matrix, int i, int j);

這個(gè)dp函數(shù)的含義如下：

從第一行（matrix[0][..]）向下落，落到位置matrix[i][j]的最小路徑和為dp(matrix, i, j) 。

根據(jù)這個(gè)定義，我們可以把主函數(shù)的邏輯寫出來：

public int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int res = Integer.MAX_VALUE;

    // 終點(diǎn)可能在最后一行的任意一列
    for (int j = 0; j < n; j++) {
        res = Math.min(res, dp(matrix, n - 1, j));
    }

    return res;
}

因?yàn)槲覀兛赡苈涞阶詈笠恍械娜我庖涣?，所以要窮舉一下，看看落到哪一列才能得到最小的路徑和。

接下來看看dp函數(shù)如何實(shí)現(xiàn)。

對(duì)于matrix[i][j]，只有可能從matrix[i-1][j], matrix[i-1][j-1], matrix[i-1][j+1]這三個(gè)位置轉(zhuǎn)移過來。

那么，只要知道到達(dá)(i-1, j), (i-1, j-1), (i-1, j+1)這三個(gè)位置的最小路徑和，加上matrix[i][j]的值，就能夠計(jì)算出來到達(dá)位置(i, j)的最小路徑和 ：

int dp(int[][] matrix, int i, int j) {
    // 非法索引檢查
    if (i < 0 || j < 0 ||
        i >= matrix.length ||
        j >= matrix[0].length) {
        // 返回一個(gè)特殊值
        return 99999;
    }
    // base case
    if (i == 0) {
        return matrix[i][j];
    }
    // 狀態(tài)轉(zhuǎn)移
    return matrix[i][j] + min(
            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        );
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

當(dāng)然，上述代碼是暴力窮舉解法，我們可以用備忘錄的方法消除重疊子問題，完整代碼如下：

public int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int res = Integer.MAX_VALUE;
    // 備忘錄里的值初始化為 66666
    memo = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(memo[i], 66666);
    }
    // 終點(diǎn)可能在 matrix[n-1] 的任意一列
    for (int j = 0; j < n; j++) {
        res = Math.min(res, dp(matrix, n - 1, j));
    }
    return res;
}

// 備忘錄
int[][] memo;

int dp(int[][] matrix, int i, int j) {
    // 1、索引合法性檢查
    if (i < 0 || j < 0 ||
        i >= matrix.length ||
        j >= matrix[0].length) {

        return 99999;
    }
    // 2、base case
    if (i == 0) {
        return matrix[0][j];
    }
    // 3、查找備忘錄，防止重復(fù)計(jì)算
    if (memo[i][j] != 66666) {
        return memo[i][j];
    }
    // 進(jìn)行狀態(tài)轉(zhuǎn)移
    memo[i][j] = matrix[i][j] + min(
            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        );

    return memo[i][j];
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

如果看過我們公眾號(hào)之前的動(dòng)態(tài)規(guī)劃系列文章，這個(gè)解題思路應(yīng)該是非常容易理解的。

那么本文對(duì)于這個(gè)dp函數(shù)仔細(xì)探討三個(gè)問題 ：

1、對(duì)于索引的合法性檢測(cè)，返回值為什么是 99999？其他的值行不行？

2、base case 為什么是i == 0？

3、備忘錄memo的初始值為什么是 66666？其他值行不行？

首先，說說 base case 為什么是i == 0，返回值為什么是matrix[0][j]，這是根據(jù)dp函數(shù)的定義所決定的 。

回顧我們的dp函數(shù)定義：

從第一行（matrix[0][..]）向下落，落到位置matrix[i][j]的最小路徑和為dp(matrix, i, j)。

根據(jù)這個(gè)定義，我們就是從matrix[0][j]開始下落。那如果我們想落到的目的地就是i == 0，所需的路徑和當(dāng)然就是matrix[0][j]唄。

再說說備忘錄memo的初始值為什么是 66666，這是由題目給出的數(shù)據(jù)范圍決定的 。

備忘錄memo數(shù)組的作用是什么？

就是防止重復(fù)計(jì)算，將dp(matrix, i, j)的計(jì)算結(jié)果存進(jìn)memo[i][j]，遇到重復(fù)計(jì)算可以直接返回。

那么，我們必須要知道memo[i][j]到底存儲(chǔ)計(jì)算結(jié)果沒有，對(duì)吧？如果存結(jié)果了，就直接返回；沒存，就去遞歸計(jì)算。

所以，memo的初始值一定得是特殊值，和合法的答案有所區(qū)分。

我們回過頭看看題目給出的數(shù)據(jù)范圍：

matrix是n * n的二維數(shù)組，其中1 <= n <= 100；對(duì)于二維數(shù)組中的元素，有-100 <= matrix[i][j] <= 100。

假設(shè)matrix的大小是 100 x 100，所有元素都是 100，那么從第一行往下落，得到的路徑和就是 100 x 100 = 10000，也就是最大的合法答案。

類似的，依然假設(shè)matrix的大小是 100 x 100，所有元素是 -100，那么從第一行往下落，就得到了最小的合法答案 -100 x 100 = -10000。

也就是說，這個(gè)問題的合法結(jié)果會(huì)落在區(qū)間[-10000, 10000]中。

所以，我們memo的初始值就要避開區(qū)間[-10000, 10000]，換句話說，memo的初始值只要在區(qū)間(-inf, -10001] U [10001, +inf)中就可以。

最后，說說對(duì)于不合法的索引，返回值應(yīng)該如何確定，這需要根據(jù)我們狀態(tài)轉(zhuǎn)移方程的邏輯確定 。

對(duì)于這道題，狀態(tài)轉(zhuǎn)移的基本邏輯如下：

int dp(int[][] matrix, int i, int j) {

    return matrix[i][j] + min(
            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        );
}

顯然，i - 1, j - 1, j + 1這幾個(gè)運(yùn)算可能會(huì)造成索引越界，對(duì)于索引越界的dp函數(shù)，應(yīng)該返回一個(gè)不可能被取到的值。

因?yàn)槲覀冋{(diào)用的是min函數(shù)，最終返回的值是最小值，所以對(duì)于不合法的索引，只要dp函數(shù)返回一個(gè)永遠(yuǎn)不會(huì)被取到的最大值即可。

剛才說了，合法答案的區(qū)間是[-10000, 10000]，所以我們的返回值只要大于 10000 就相當(dāng)于一個(gè)永不會(huì)取到的最大值。

換句話說，只要返回區(qū)間[10001, +inf)中的一個(gè)值，就能保證不會(huì)被取到。

至此，我們就把動(dòng)態(tài)規(guī)劃相關(guān)的三個(gè)細(xì)節(jié)問題舉例說明了。

拓展延伸一下，建議大家做題時(shí)，除了題意本身，一定不要忽視題目給定的其他信息 。

本文舉的例子，測(cè)試用例數(shù)據(jù)范圍可以確定「什么是特殊值」，從而幫助我們將思路轉(zhuǎn)化成代碼。

除此之外，數(shù)據(jù)范圍還可以幫我們估算算法的時(shí)間/空間復(fù)雜度。

比如說，有的算法題，你只想到一個(gè)暴力求解思路，時(shí)間復(fù)雜度比較高。如果發(fā)現(xiàn)題目給定的數(shù)據(jù)量比較大，那么肯定可以說明這個(gè)求解思路有問題或者存在優(yōu)化的空間。

除了數(shù)據(jù)范圍，有時(shí)候題目還會(huì)限制我們算法的時(shí)間復(fù)雜度，這種信息其實(shí)也暗示著一些東西。

比如要求我們的算法復(fù)雜度是O(NlogN)，你想想怎么才能搞出一個(gè)對(duì)數(shù)級(jí)別的復(fù)雜度呢？

肯定得用到 二分搜索或者二叉樹相關(guān)的數(shù)據(jù)結(jié)構(gòu)，比如TreeMap，PriorityQueue之類的對(duì)吧。

再比如，有時(shí)候題目要求你的算法時(shí)間復(fù)雜度是O(MN)，這可以聯(lián)想到什么？

可以大膽猜測(cè)，常規(guī)解法是用 [回溯算法暴力窮舉，但是更好的解法是動(dòng)態(tài)規(guī)劃，而且是一個(gè)二維動(dòng)態(tài)規(guī)劃，需要一個(gè)M * N的二維dp數(shù)組，所以產(chǎn)生了這樣一個(gè)時(shí)間復(fù)雜度。

如果你早就胸有成竹了，那就當(dāng)我沒說，畢竟猜測(cè)也不一定準(zhǔn)確；但如果你本來就沒啥解題思路，那有了這些推測(cè)之后，最起碼可以給你的思路一些方向吧？

總之，多動(dòng)腦筋，不放過任何蛛絲馬跡，你不成為刷題小能手才怪。