遞推算法與遞推套路(手撕算法篇)

語言: CN / TW / HK

之前學習基礎知識的時候也説了,遞推和動態規劃有這曖昧不清的關係,可以説,動態規劃就是多了一個決策過程的遞推。因此,我們今天的刷題也會涉及到一些比較簡單的動態規劃的題目,同樣能夠對我們深刻的理解遞推算法起到幫助,也為我們之後深入學習動態規劃算法和動態規劃的優化打下基礎。

作者/ 湯文輝

編輯/ 劉振宇

youdao

一、前置知識

ydtech

1.1

滾動數組

使用場景:當我們下(上)一行的狀態可以僅僅通過上(下)一行的信息推導出來,並要求我們求解最後(第)一行時,我們無需將每一行的數據都存儲在數組當中,可以通過滾動數組的技巧,節省空間複雜度。

具體實現:假設我們已經知道第一行的數據,並且通過第一行數據經過一定的運算可以得到第二行的數據,那麼,我們只需要一個數組臨時存儲兩行數據,就可以將之後的每一行數據的結果計算出來,不斷的滾動替換這兩行數據,最終求解出最後一行數據的方式。

關鍵點:推導計算當前行和下(上)一行的索引。由於數組是滾動的,因此,我們目標行的索引也是隨時變化的,以下為求取當前行和上(下)一行的通用公式:

當前行: const curIdx = i % 2

由於我們的滾動數組只有2行,因此,當前索引只要與2求模即可;

上(下)一行:const preIdx = +!curIdx

由於滾動數組只有兩行,索引要麼是0,要麼是1,我們對當前行取反便可得到上(下)一行的索引(注意,在js中,對1取反是false,對0取反是true,因此我們通過一個隱式類型轉換將布爾類型轉換為數字類型)。

實際使用:後面刷題時會經常用到,詳見下文。

youdao

二、刷題正餐

ydtech

2.1

LeetCode 120. 三角形最小路徑和


2.1.1 解題思路

按照我們之前將的遞推套路:

1. 定義遞推狀態:在這道題中,我們每走一步的路徑和主要取決於當前所處的行數i和當前的列數j,因此,我們這道題的遞推狀態應該是:dp[i, j]

2. 遞推公式:確定了遞推狀態之後,我們就要確定遞推公式了。那麼,第i行第j列的數據要如何才能推導出來呢?首先,依據題意,我們要求最小路徑和,如果我們從最底下往上走,那麼我們可以知道,下一行i的數據應該是上一行i+1合法路徑的最小值加上當前走到節點的值。

因此,我們得到了如下公式:

// 第i行第j列數據的推導公式
dp[i, j] = min(dp[i+1, j], dp[i+1, j+1]) + val[i,j]

3. 分析邊界條件:我們需要將我們題目已知的條件初始化到我們的遞推數組當中作為邊界條件。這道題中,邊界條件就是最後一行的數據,我們將最後一行的數據先加入到滾動數組當中,這樣之後就可以根據最後一行數據不斷的往上推導總路徑和,從而找到最小路徑。

4. 程序實現:我們直接使用循環加滾動數組技巧實現。


2.1.2 代碼演示


function minimumTotal(triangle: number[][]): number {    const n = triangle.length; 
    // 遞推公式(狀態轉義方程)以下為自底向上走的公式
    // dp[i, j] = min(dp[i+1, j], dp[i+1, j+1]) + val[i,j]
    // 由於i只跟i+1有關,因此,我們可以用滾動數組的技巧定義dp數組
    let dp: number[][] = [];
    for(let i=0;i<2;i++){
    dp.push([]);
    }
    // 首先初始化最後一行的數值,由於使用了滾動數組的技巧,因此,我們最後一行的索引應該是(n-1)%2
    for(let i=0;i<n;i++) {
    dp[(n-1)%2][i] = triangle[n-1][i];
    }
    // 然後從倒數第二行開始求值
    for(let i = n-2;i>=0;--i) {
        // 由於使用了滾動數組,因此,當前行的下標為i%2,而下一行的下標則是當前行下標取反
        let idx = i % 2;
        let nextIdx = +!idx;
        // 根據上面的公式計算出每一個位置上的值
        for (let j=0; j <= i; j++) {
            dp[idx][j] = Math.min(dp[nextIdx][j], dp[nextIdx][j + 1]) + triangle[i][j];
        }
    }
    // 最終,三角形頂點的那個值就是我們要求的值
    return dp[0][0];
};


2.2

LeetCode 119. 楊輝三角 II


2.2.1 解題思路

這道題與上一道題類似,依然可以根據上一行推導出下一行的值,因此還是要祭出滾動數組的技巧,遞推狀態與遞推公式的分析也比較類似,大家可以自己嘗試推導。

而這一道題的邊界條件,其實就是每一行的第一位都應該是1。


2.2.2 代碼演示


function getRow(rowIndex: number): number[] {
    const res: number[][] = [];
    // 初始化兩行全部初始填充0的滾動數組
    for(let i=0;i<2;i++)res.push(new Array(rowIndex+1).fill(0));
    for(let i=0;i<=rowIndex;i++) {
        // 計算滾動數組當前索引和上一行索引
        let idx = i % 2;
        let preIdx = +!idx;
        res[idx][0] = 1;
        // 計算每一行出第一位外其他位置的值
        for(let j=1;j<=i;j++) {
            res[idx][j] = res[preIdx][j-1] + res[preIdx][j];
        }
    }
    // 滾動數組最後一行
    return res[(rowIndex % 2)]
};


2.3

LeetCode 198. 打家劫舍


2.3.1 解題思路


1. 遞推狀態分析:既然要求能夠偷到的最多的金額,那麼,假設最後一家是n,那麼,最大金額與我們是否偷最後一家有直接的關係,我們需要分類討論:

    a. 不偷最後一家:dp[n][0]其中,0代表不偷

    b. 偷最後一家:dp[n][1]其中,1代表偷

2. 確定遞推公式:由於遞推狀態分為兩種情況討論,因此,我們的遞推公式,也應該分成兩個部分:

    a. 不偷最後一家:由於不能連續偷相鄰的兩家,如果最後一家不偷,那麼,我們倒數第二家就可以偷,因此,此時我們的最大收益就取決於偷倒數第二家的金額與不偷倒數第二家金額的最大值。即:dp[n][0] = max(dp[n-1][0], dp[n-1][1])

    b. 偷最後一家:由於要偷最後一家,那麼就不能偷倒數第二家,因此,這種情況的最大收益是不偷倒數第二家獲得的收益加上偷最後一家帶來的收益,即dp[n][1] = dp[n-1][0] + nums[n]

3. 確定邊界條件:

依據題意,我們如果不偷第一家的時候,因為一家都沒偷,此時收益應該為0。如果偷第一家,那麼收益就是第一家的錢。至此,我們就確立了最開始的邊界條件。

4. 程序實現:這道題由於當前收益只取決於上一家的收益,因此依然使用滾動數組技巧加循環實現。


2.3.2 代碼演示


function rob(nums: number[]): number {
    const n = nums.length;
    // 由於不能連續偷兩家,因此,最大收益應該分為兩種情況討論:
    // 1. dp[n][0] = max(dp[n-1][0], dp[n-1][1]) 即:不偷最後一家的最後收益,取決於我偷倒數第二家的收益與不偷倒數第二家的收益的最大值
    // 2. dp[n][1] = dp[n-1][0] + nums[n] 即:如果投了最後一家,那麼倒數第二家就不能偷,所以最大收益就等於不偷倒數第二家的收益加上偷最後一家獲得的收益
    const dp: number[][] = [];
    for(let i=0;i<2;i++) dp.push([]);
    // 初始化第0家的值
    dp[0][0] = 0;// 不偷第一家時收益為0
    dp[0][1] = nums[0];// 偷第一家時收益為第一家的錢
    for(let i=1;i<n;i++) {
// 使用滾動數組技巧
        let idx = i % 2;
        let preIdx = +!idx;
        dp[idx][0] = Math.max(dp[preIdx][0] , dp[preIdx][1]);
        dp[idx][1] = dp[preIdx][0] + nums[i];
    }
    // 最終收益最大值時不偷最後一家和偷最後一家的最大值
    return Math.max(dp[(n-1) % 2][0], dp[(n-1) % 2][1]);
};


2.4

LeetCode 152. 乘積最大子數組


2.4.1 解題思路

1. 遞推狀態分析:  我們要求最大子數組的乘積,那麼我們可以用  dp[n]  代表最後一位是  的最大子數組乘積最大值。
2. 遞推公式:  最後一個數是  有兩種可能性,第一種是讓  n-1  的最大乘積再乘上當前n的值,第二種則是  不與之前的值相乘,自開一國,因此,我們應該在這兩種情況中選一個最大值,所以,遞推公式應為: dp[n] = max(dp[n-1] * val[n], val[n])
3. 邊界條件: 由於數組中可能含有負數,有可能使當前值乘上原先的最大值變成最小值,也可能時當前值乘上原先的最小值變成最大值,因此,我們不僅需要記錄當前數字之前的最大值,也要記錄最小值,方便處理負數的情況。而初始時,由於我們要求的是乘積關係,那麼我們的最大值和最小值都初始化為1即可。
4. 程序實現: 由於第  項的最大乘積只跟  n-1  有關,我們可以使用變量方式存儲關係,不需要額外開闢遞推數組空間。


2.4.2 代碼演示


function maxProduct(nums: number[]): number {
    // 遞推狀態:dp[n]代表以n作為結尾的最長連續子數組的乘積
    // 遞推公式:dp[n] = max(dp[n-1] * val[n], val[n]),即這個有兩種可能,一種是以n作為結尾,然後乘上之前的最大值,另一種是不乘之前的值,自己獨立成為一個結果
    // 我們應該從這兩種方案中選擇一個較大的值作為結果
    // 由於當前值只跟上一個值有關,我們可以使用變量方式來替代遞推數組,又因為數組中可能存在負數,有可能導致當前值乘上之前的最大值變成了最小值,因此,我們
    // 還需要額外記錄一下數組中的最小值
    let res = Number.MIN_SAFE_INTEGER;
    // 由於是乘積關係,因此,最小值和最大值初始化為1
    let min = 1;
    let max = 1;
    for(let num of nums) {
        // 由於num是小於0的,因此,如果我們依然乘以原先的最大值,那就可能反而變成最小值,因此當num小於0時,我們交換最大值和最小值,這樣,num乘以原先的最小值,就可以得到較大值了
        if(num < 0) [min, max] = [max, min];
        // 計算最大值和最小值
        min = Math.min(min * num, num);
        max = Math.max(max * num, num);
        // 最終結果在上一個結果和max間取最大值
        res = Math.max(res, max);
    }
    return res;
};


2.5

LeetCode 322. 零錢兑換


2.5.1 解題思路

1. 遞推狀態: 我們使用多少個硬幣,取決於要湊的金額的面額有多大,因此,我們的遞推狀態為: dp[n]
2. 遞推公式: 假如我們要湊的面額是 n ,那麼我們能湊夠的最小的硬幣數量應該是 n-coin 面額硬幣數量再加上當前這枚硬幣 coin 的數量1,並且每次都取最少的數量即可。因此,我們最終的遞推公式應該是: dp[n] = min(dp[i-coin] + 1), 即面額為 n 的錢需要我們在所有的拼湊方案中,取一個最小值,而每一個拼湊方案應該是當前面額i減去當前使用的硬幣面額 coin 再加上當前硬幣的數量 1
3. 邊界條件: 當面額為0時,我們需要0枚硬幣。
4. 程序實現: 我們再拼湊面額的時候,有一些特殊情況需要考慮,如:
如果當前要拼湊的面額比硬幣的面額要小,那麼我們無法使用當前硬幣拼湊成目標面額
如果 i-coin 面額都無法拼湊成功的話,那麼我們肯定也無法使用 coin 面額的硬幣拼湊出目標面額,因為 i-coin 是前置條件。


2.5.2 代碼演示


function coinChange(coins: number[], amount: number): number {
    // 我們需要計算出每一個面額所需要的硬幣數量
    let dp: number[] = new Array(amount+1);
    // 初始時全部填充為-1代表不可達
    dp.fill(-1);
    // 拼湊0元需要0枚硬幣
    dp[0] = 0;
    // 循環每一個面額
    for(let i=1;i<=amount;i++) {
        for(let coin of coins) {
            // 如果當前要拼湊的面額比當前硬幣還小,那就不能使用當前硬幣
            if(i < coin) continue;
            // 如果沒辦法拼湊到dp[i-coin]的硬幣,那麼自然也不可能使用coin面額的硬幣拼湊到dp[i]
            if(dp[i - coin] === -1) continue;
            // 如果當前的匹配方案沒有使用過,或者使用當前匹配方案的結果比上一個匹配方案的結果大,説明我們找到了更小的拼湊方案,那麼我們就把當前拼湊方案替換之前的拼湊方案
            if(dp[i] === -1 || dp[i] > dp[i - coin] + 1) dp[i] = dp[i - coin]+1;
        }
    }
    return dp[amount];
};


2.6

LeetCode 300. 最長遞增子序列


2.6.1 解題思路


>>概念掃盲:

a. 遞增子序列:

你可以在一個完整的序列中,“跳着”選擇元素,並且下一個元素必須不能小於上一個元素。所謂“跳着”,就是指元素索引不需要連續,如下面示例:

# 原始序列

1, 4, 2, 2, 3, 5, 0, 6

# 遞增子序列

1, 2, 2, 3, 5, 6

b. 嚴格最長遞增子序列:

嚴格遞增子序列是在遞增子序列的基礎上多了一個限定條件,就是下一個元素不能等於上一個元素,只能大於,如下示例:

# 原始序列

1, 4, 2, 2, 3, 5, 0, 6

# 嚴格遞增子序列

1, 2, 3, 5, 6

1. 遞推狀態: 由於我們最長遞增子序列的長度與我當前以哪個元素作為最後一個元素有關,因此,我們的遞推狀態為: dp[n] ,代表以n位置作為結尾的最長遞增子序列的長度
2. 遞推公式: 我們要算出以第n個元素作為結尾的最長遞增子序列的長度,就要找出他上一個合法的最長遞增子序列的最後一個元素j,而我們第n個元素作為結尾的最長遞增子序列長度就是上一個最長遞增子序列長度加一,我們只需要將所有滿足這個條件的最長遞增子序列長度的最大值求出來就是最終的結果,即: dp[n] = max(dp[j] + 1) | j<n & val(j) < val(n)
3. 邊界條件: n為1時,最長遞增子序列長度為1
4. 程序實現: 由於我們的遞歸狀態定義的是以n作為結尾的最長遞增子序列的長度,因此,我們每一項的初始值默認都是1,至少要選擇當前的數。


2.6.2 代碼演示


function lengthOfLIS(nums: number[]): number {
    const dp: number[] = [];
    let res: number = Number.MIN_SAFE_INTEGER;
    for(let i=0;i<nums.length;i++) {
 // 每一項都初始化為1,因為dp[i]代表以i位置作為結尾的最長遞增子序列的長度,那我們最少都應該選擇i這個數,長度就是1
        dp[i] = 1;
        // 在i位置之前找到滿足nums[j] < num[i]的值
        for(let j = 0; j < i;j++) {
            if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        // 到此,我們已經找到了一組最長遞增子序列了,更新一下res
        res = Math.max(res, dp[i]);
    }
    return res;
};


youdao

三、結語

ydtech

今天的刷題到此暫告一段落。

從上面刷的幾道題其實我們不難發現,無論是遞推算法還是動態規劃,都有一定的套路可循,雖然這個套路學起來也並不簡單,但是至少有了明確的學習方向,我們可以通過:遞推狀態定義、遞推公式(狀態轉移方程)推導、邊界條件確立、程序實現這四個通用套路將一個看似複雜的遞推或動規程序逐一分析解決。

當然,上面的程序實現,為了更容易理解,沒有使用太多的技巧進行優化,並不一定是最優的,未來如果有機會,將和大家分享動態規劃的優化技巧。也歡迎大家與我們多多交流~

- END -



往期推薦


本文分享自微信公眾號 - 有道技術團隊(youdaotech)。
如有侵權,請聯繫 [email protected] 刪除。
本文參與“OSC源創計劃”,歡迎正在閲讀的你也加入,一起分享。