一、前言

本文要為大家?guī)淼氖莇p動態(tài)規(guī)劃，相信這是令很多同學頭疼的一個東西，也是在大廠面試中很喜歡考的一個經典算法

?? 本文總共會通過四道題來逐步從淺至深地帶讀者逐步認識dp動態(tài)規(guī)劃

二、動態(tài)規(guī)劃理論基礎

首先在講解題目之前，我們要先來說說動態(tài)規(guī)劃理論基礎，讓大家知道到底什么是【動態(tài)規(guī)劃】

1、基本概念

動態(tài)規(guī)劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態(tài)規(guī)劃是最有效的。

• 如果讀者有學習過【貪心算法】的話，就可以知道其和動態(tài)規(guī)劃是很類似的，但是呢卻有著本質的區(qū)別，對于 貪心 而言，是 局部直接選最優(yōu)，但是對于 動規(guī) 而言則是 通過上一個狀態(tài)去推導出下一個狀態(tài)

例如：有N件物品和一個最多能背重量為W 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大

1. 本題若是使用 動態(tài)規(guī)劃 來做，需要先表示出數(shù)組dp的狀態(tài)，通過dp[j-weight[i]]推導出dp[j]，然后得出 狀態(tài)轉移方程max(dp[j], dp[j - weight[i]] + value[i])，才能計算出最終的結果
2. 但若是使用 貪心算法 來求解的話，直接在每次拿物品選一個最大的或者最小的就完事了

?? 所以大家在做題的時候只要牢牢記住它們而言的最本質區(qū)別即可，題目刷多了，自然也就很好區(qū)分

2、動態(tài)規(guī)劃五部曲【?】

清楚了動態(tài)規(guī)劃的基本概念后，我們再來看看在解決動態(tài)規(guī)劃的問題時的解題步驟??

• 做動規(guī)題目的時候，很多同學會陷入一個誤區(qū)，就是以為把 狀態(tài)轉移公式 背下來，照葫蘆畫瓢改改，就開始寫代碼，甚至把題目AC之后，都不太清楚dp[i]表示的是什么
• 所以遇到一些同種類的其他題目時，就會手足無措，狀態(tài)轉移公式（遞推公式）是很重要，但動規(guī)不僅僅只有遞推公式。對于動態(tài)規(guī)劃問題，我將拆解為如下五步曲：
  1. 確定dp數(shù)組（dp table）以及下標的含義
  2. 確定遞推公式（狀態(tài)轉移方程）
  3. dp數(shù)組如何初始化
  4. 確定遍歷順序，對dp數(shù)組進行填表
  5. 確認返回值 / 輸出內容

一些同學可能想為什么要先確定遞推公式，然后再考慮初始化呢？

• 因為一些情況是遞推公式決定了dp數(shù)組要如何初始化！

所以我們要先根據(jù)dp的狀態(tài)，來推導出狀態(tài)轉移方程，接著再通過去分析這個方程，然后推敲出dp數(shù)組要怎樣去做一個初始化才比較合適，不會導致越界的問題。所以對于那些只知道記公式但是不知道如何初始化和遍歷數(shù)組的同學，就會顯得尷尬

3、出錯了如何排查？

相信大家在寫代碼的時候一定會出現(xiàn)各種各樣的Bug，那要如何去解決呢，還記得之前的 LeetCode轉VS調試技巧 嗎？

• 但是對于動態(tài)規(guī)劃而言，就是在力扣中 把dp數(shù)組打印出來，看看究竟是不是按照自己思路推導的！。這是最簡潔明了的方式，所以我們遇到問題后不要害怕，而是要逐步地去分析、排查問題，加強自己排查錯誤的能力，如果還是不會了再去請教別人，但是在請教之前也先請問問自己下面的三個問題：
  1. 這道題目我舉例推導狀態(tài)轉移公式了么？
  2. 我打印dp數(shù)組的日志了么？
  3. 打印出來了dp數(shù)組和我想的一樣么？
• 把上面三個問題想明白之后再去問別人，即經過了自己的思考之后，有了自己的見解，這樣才能更有效果，并且做到事半而功倍

三、實戰(zhàn)演練??

在了解了一些動態(tài)規(guī)劃的基礎理論之后，我們還是要進入實際的問題

0x00 斐波那契數(shù)

原題傳送門：力扣509.斐波那契數(shù)

首先第一道動態(tài)規(guī)劃的入門題必須選擇的就是【斐波那契數(shù)】，下面我會給出三種解法

• 首先是最簡單的一種，即 遞歸解法，不做詳細展開，不懂可以看看 C語言函數(shù)章節(jié) 中的函數(shù)遞歸，就會很清楚了

class Solution {
public:
    int fib(int n) {
        if(n < 2)   return n;
        return fib(n - 1) + fib(n - 2);
    }
};

接下去的話就是我們本題的重點即 動態(tài)規(guī)劃 的解法

1. 首先的話就是要去創(chuàng)建dp數(shù)組，這里使用到的是 C++STL之vector類，如果有不懂的同學可以去看看，我們初始化出一個大小為n + 1的數(shù)組

vector<int> dp(n + 1);

2. 接下去我們要去做的就是要去推導出這個 狀態(tài)表示方程，那對于斐波那契數(shù)列我們很熟悉，后一個數(shù)等于前兩個數(shù)之和，而且后面的數(shù)依賴于前面的數(shù)，所以我們的遍歷數(shù)組也應該是從左向右

dp[i] = dp[i - 2] + dp[i - 1];

3. 再者我們就需要通過上面這個 狀態(tài)表示方程 來對這個dp數(shù)組去做一個初始化的工作，此時我們需要去考慮的就是這個越界的問題，因為當前的dp[i]依賴的是前兩個數(shù)，所以若此刻的i == 0的話，前兩個數(shù)就會發(fā)生越界的情況；若是i == 1，第一個數(shù)就會發(fā)生越界，所以 我們要對前兩個數(shù)做一個初始化的操作

dp[0] = 0, dp[1] = 1;

4. 那在初始化完成之后，我們就可以去做遍歷填表的工作了，因為前兩個數(shù)字已經被初始化了，所以從下標為2的地方開始向后遍歷

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

5. 當遍歷填表結束后，因為所求的是第N個斐波那契數(shù)，所以我們就需要去返回dp[n]

return dp[n];

以下即為整體代碼展示

class Solution {
public:
    int fib(int n) {
        if(n <= 1)  return n;

        // 1.創(chuàng)建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[0] = 0, dp[1] = 1;

        // 3.遍歷填表
        for(int i = 2; i <= n; ++i)
        {
            dp[i] = dp[i - 2] + dp[i - 1];
        }

        // 4.返回值
        return dp[n];
    }
};

讀者可以通過執(zhí)行結果來看看dp動態(tài)規(guī)劃解法的優(yōu)勢

再下面一種方法則是通過 滾動數(shù)組 的形式進行求解

• 可能讀者有所不太理解什么是【滾動數(shù)組】，如果你了解迭代算法的話就可以知道，其實并不復雜。原理也是一樣的，我們直接通過定義一維數(shù)組

int dp[2];

• 然后將上面dp動態(tài)規(guī)劃中的 遞推公式 轉換成迭代的形式即可

for(int i = 2; i <= n; ++i)
{
    sum = dp[0] + dp[1];
    // 迭代
    dp[0] = dp[1];
    dp[1] = sum;
}

其余的沒有大變化，代碼如下：

class Solution {
public:
    int fib(int n) {
        if(n <= 1)  return n;
        int sum = 0;
        int dp[2];      // 一維數(shù)組模擬
        dp[0] = 0, dp[1] = 1;

        for(int i = 2; i <= n; ++i)
        {
            sum = dp[0] + dp[1];
            // 迭代
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];   // 最后累加的結果存入了dp[1]
    }
};

稍做了一些優(yōu)化，看看運行效率

0x01 第N個泰波那契數(shù)

原題傳送門：力扣1137.第 N 個泰波那契數(shù)

看完斐波那契數(shù)之后，我們再來看一個東西叫做【泰波那契數(shù)】，不知讀者有否聽說過呢？

1、題目解讀

首先我們來解讀一下本題的意思??

• 相信讀者在看到【泰波那契數(shù)】的時候，不禁會聯(lián)想到【斐波那契數(shù)】，它們呢是一對孿生兄弟，這個 泰波那契數(shù) 相當于是 斐波那契數(shù) 的加強版
• 我們首先可以來看到這個遞推公式Tn+3 = Tn + Tn+1 + Tn+2，讀者可能看不太懂，我們將其做一個轉換為Tn = Tn-1 + Tn-2 + Tn-3，即把所有n都統(tǒng)一-3。那么第N個泰波那契數(shù)就等于前面3個泰波那契數(shù)的和

• 看到上面的T3，就是前3個數(shù)的和等于2，以此類推T4就是T1 + T2 + T3 = 4

2、解題方法

看完了上面對于題目的分析之后，下面我將介紹兩種解法

① dp動態(tài)規(guī)劃

首先的話就是本題需要掌握的重點即【動態(tài)規(guī)劃】的解法，我們要分成五步去求解

1. 狀態(tài)表示

• 首先讀者要清楚的是在求解動態(tài)規(guī)劃的題目時，都是需要一個dp數(shù)組的，那么對于【狀態(tài)表示】的含義就是dp表里的值所表示的含義

那這個狀態(tài)表示是怎么來的呢？

① 第一個呢就是按照題目要求來，即dp[i]表示的就是第i個泰波那契數(shù)列的值

② 第二個呢則是需要讀者有豐富的刷題經驗，可以讀完題目之后就得出對應的結果

③ 第三個呢則是在分析問題的過程中，發(fā)現(xiàn)重復的子問題

如果讀者之前有接觸過類似的動態(tài)規(guī)劃問題的話，就會看到一些題解里講：這道題的 狀態(tài)表示 是怎樣的，然后就直接講本題的 狀態(tài)表示方程，根本沒有說這道題的狀態(tài)表示是怎么來的。這個得來的過程我會在其他動態(tài)規(guī)劃的題目中進行講解

?? 所以讀者在解類似的問題時一定要知道下面的這個【狀態(tài)表示方程】是怎么來的，做到 “ 知其然，知其所以然 ”

2. 狀態(tài)表示方程

• 那么本題的狀態(tài)表示方程為dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

3. 初始化

• 在清楚【狀態(tài)表示方程】該如何寫之后，我們要去做的就是對這個dp數(shù)組做一個初始化的工作?？吹较旅娴倪@個dp數(shù)組，如果在一開始我們的下標取值就到0的話，那么i - 1、i - 2、i - 3這些就會造成 越界

• 因此我們要給這個dp數(shù)組去做一個初始化，具體的就是對前三個數(shù)據(jù)即dp[0]、dp[1]、dp[2]分別初始化為【0】【1】【1】，那我們在后面遍歷計算的時候就只需要從下標為3的位置開始即可

 dp[0] = 0, dp[1] = dp[2] = 1;

4. 填表順序

• 接下去的話就是把dp數(shù)組按照 狀態(tài)表示方程 給填充好即可

for(int i = 3; i <= n; ++i)
{
    // 狀態(tài)轉移方程
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}

5. 返回值

• 最后一塊我們處理返回值，根據(jù)題目要求我們是要返回【第 n 個泰波那契數(shù) Tn 的值】，所以直接 return dp[n] 即可

但是呢，若只考慮上面的這一些，在提交的時候是會出現(xiàn)越界的情況，因為在題目中給出的n的范圍為[0, 37]，因此對于dp[0]還好說，但對于后面的數(shù)據(jù)就會出現(xiàn)越界的情況

因此我們還需要去考慮一些邊界的問題

// 邊界問題處理
if(n == 0)  return 0;
if(n == 1 || n == 2)    return 1;

?? 整體代碼會在最后給出

② 迭代優(yōu)化?

看完上面這一種，我們再來看看其是否可以去做一個優(yōu)化

• 如果讀者有接觸過迭代算法的話，應該很快能想到本題的思路，因為是三個三個去做的累加，所以我們在這里可以定義三個變量a、b、c，它們累加后的值可以放到變量d中

• 因此在累加完一輪之后，我們就需要去做一個迭代的操作

a = b; b = c; c = d;

• 那么在最后我們所需要返回的值就是這個d

return d;

3、復雜度

• 時間復雜度:

對于第一種dp的解法，其時間復雜度為$O(n)$，而對于第二種迭代的解法時間復雜度為$O(1)$

• 空間復雜度:

對于第一種dp的解法，其空間復雜度為$O(n)$，而對于第二種迭代的解法時間復雜度為$O(1)$

?? 所以就這么對比下來迭代優(yōu)化的方法還是值得大家去掌握的

4、Code

首先是第一種dp動態(tài)規(guī)劃的解法

class Solution {
public:
    int tribonacci(int n) {
        // 邊界問題處理
        if(n == 0)  return 0;
        if(n == 1 || n == 2)    return 1;
        // 1.創(chuàng)建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[0] = 0, dp[1] = 1, dp[2] = 1;

        // 3.填表
        for(int i = 3; i <= n; ++i)
        {
            // 狀態(tài)轉移方程
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        // 4.返回值
        return dp[n];
    }
};

然后的話是第二種利用迭代優(yōu)化的方法

class Solution {
public:
    // 空間優(yōu)化
    int tribonacci(int n) {
        // 特殊情況處理
        if(n == 0)  return 0;
        if(n == 1 || n == 2)    return 1;
        int a = 0, b = 1, c = 1, d = 0;
        for(int i = 3; i <= n; ++i)
        {
            d = a + b + c;
            // 迭代
            a = b; b = c; c = d;
        }
        return d;
    }
};

0x02 爬樓梯

原題傳送門：力扣70.爬樓梯

我們再來看一道和斐波那契數(shù)很像的題目，看了代碼后你就會有這樣的感覺

• 題目意思很簡單，若是你現(xiàn)在在爬樓梯的話，每次只能上1 / 2個臺階，請問上到第N個臺階有多少種不同的方法。這個其實也和【青蛙跳臺階】非常得類似，不過在那個時候我們是使用 遞歸 來進行求解的，這里我們要考慮使用dp動態(tài)規(guī)劃

• 不必多解釋，直接上代碼，這里唯一要注意的一點就是在初始化的時候是要去初始化dp[1]和dp[2]，而不是去初始化dp[0]，因為臺階并沒有0號臺階，而是從1號開始

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2)  return n;
        vector<int> dp(n + 1);
        dp[1] = 1;  // 從第一層樓梯開始初始化
        dp[2] = 2;

        for(int i = 3; i <= n; ++i)
        {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
};

0x03 三步問題

原題傳送門：面試題0801.三步問題

看完了爬樓梯之后，我們再來做一個進階，解決一個三步問題

• 首先來看一下題目所描述的意思，剛才我們一次是只能上1階、2階，現(xiàn)在的話是可以上3階了，那么爬樓梯的種類就會增多

• 那我們先來分析一下，到[1]號臺階有1種方法，到[2]號臺階有2種方法，分別是1 1和0 2，到[3]號臺階則是有1 1 1、0 2 1、0 1 2、0 3，可以看做是【1 + 1 + 2 = 4】，那么以此類推到達第4號臺階即為【1 + 2 + 4 = 7】

那分析完題目后我們就要根據(jù)動規(guī)五部曲來完成對題目的分析

• 首先第一步就是需要去確定狀態(tài)表示，那經過我們的分析，本題的dp[i]表示的就是 到達 i 位置時，一共有多少種方法

• 接下去呢我們就需要通過這個i位置的狀態(tài)以及dp數(shù)組的含義，去進一步劃分思考問題 。那根據(jù)題目中來看，因為是需要走三步，我們從i位置往前推出i - 3、i - 2、i - 1這三個位置

• 那么從這三個位置到下標為i的位置即為dp[i - 1]、dp[i - 2]、dp[i - 3]
• 很明顯我們就可以推出狀態(tài)轉移方程為：

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

• 接下去呢我們就需要去考慮初始化的問題了，主要是要考慮到 越界 這一塊的問題，這個我在講解前面的題目時也有講到過，因為不存在0號臺階，所以當此時的 i == 1 的話，前面的三個數(shù)就會發(fā)生越界的問題

• 那我們就可以對這三個位置去做一個初始化的工作了

• 接下去我們要來確立的就是填表順序了，上面說到過這個i位置的值依賴于前3個值，所 以我們的填表順序就需要【從左往右】來進行

• 那么最后的返回值即為dp[n]

• 根據(jù)上面的五部曲，我們先來看看代碼該如何去進行書寫

class Solution {
public:
    int waysToStep(int n) {
        // 1.創(chuàng)建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;

        // 3.填表
        for(int i = 4; i <= n; ++i)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        // 4.返回值
        return dp[n];
    }
};

• 首先第一個問題就是很明顯的越界問題，反應快的同學應該很快就可以察覺到時前面三個位置的問題

• 所以我們應該在最前面加上這樣的一些判斷

// 考慮越界問題
if(n == 1 || n == 2) return n;
if(n == 3)  return 4;

• 但是呢，在提交之后發(fā)現(xiàn)還有錯誤存在：仔細觀察的話發(fā)現(xiàn)這是一個 運行時異常，叫做signed integer overflow —— 有符號數(shù)的整數(shù)溢出

原題：結果可能很大，你需要對結果模1000000007

• 如果讀者對題目本身還有印象的話就可以知道本題的結果可能會很大，所以題目中講到要我們去做【取?！康倪\算

這里我們先去定義一個常量，因為對于1000000007它的值的即為1e9 + 7

// 定義常量
const int MOD = 1e9 + 7;

然后在填表遍歷的時候就可以去對所計算出來的值做一個取余的操作

dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;

以下即為整體的代碼展示：

class Solution {
public:
    int waysToStep(int n) {
        // 定義常量
        const int MOD = 1e9 + 7;

        // 考慮越界問題
        if(n == 1 || n == 2) return n;
        if(n == 3)  return 4;
        // 1.創(chuàng)建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;

        // 3.填表
        for(int i = 4; i <= n; ++i)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }

        // 4.返回值
        return dp[n];
    }
};

然后就看到很順利地通過了

0x04 使用最小花費爬樓梯?

原題傳送門：746.使用最小花費爬樓梯

知道了怎么去爬樓梯之后，我們再來做一個進階：如何利用最小的花費去爬樓梯，本題很鍛煉大家的dp思維，準備好，發(fā)車了??

• 首先我們來分析一下題目的意思，就是我們在向上爬樓梯的時候，需要去支付一定的費用；可以選擇從 下標為 0 或下標為 1 的臺階開始爬樓梯，題目要我們計算的就是 怎樣去爬才可以使得爬到樓頂所需要花費的最少
• 在這里讀者尤其要注意的一個點是關注樓頂在哪里，仔細看示例就可以發(fā)現(xiàn)樓頂應該是在cost[n]的位置才對

解法一

接下去我們就可以開始通過一步一步地去進行求解

• 首先還是一樣，我們要去定義dp數(shù)組并且了解這個dp[i]所表示的含義是什么，即到達i位置時的最小花費

• 接下去呢，我們就要通過當前的這個i的位置之前或者之后的狀態(tài)去推導出【狀態(tài)轉移方程】，來表示dp[i]

• 因為我們可以選擇向上爬一個或者兩個臺階，所以就將求解dp[i]轉換為了兩個子問題：
  1. 先到達 i - 1 位置，然后支付 cost[i - 1]，走一步
  2. 先到達 i - 2 位置，然后支付 cost[i - 2]，走二步
• 可以看到，因為我們在到達一個臺階時，需要支付完一筆費用后才能前行，那么前者可以轉換為dp數(shù)組 —— 到達 i 位置的最小花費來表示；后者的話則可以轉換為cost數(shù)組 —— 從每個臺階上爬需要支付的費用

• 雖然是分成了兩個子問題來進行求解，但是呢題目給我們的要求是最小花費，所以我們應該要取的是二者之中的較小值。那么【狀態(tài)轉移方程】即為

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

• 那么當這個【狀態(tài)轉移方程】寫出來后我們就要去考慮這個 初始化 的問題了，因為上 0號 和 1號 臺階的時候我們是不需要支付任何費用的，并且為了防止不越界，我們在初始化的時候應該令dp[0] = dp[1] = 0

• 接下來的話就要去考慮我們的填表順序了，因為dp[i]是依賴于dp[i - 1]和dp[i - 2]，所以我們需要先算出前面的2個數(shù)才能去得到這個dp[i]，因此這個填表的順序應該是 從左向右

• 最后的話就是我們的返回值dp[n]了

以下就是代碼了

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        if(n <= 1)  return n;
        // 1.定義dp數(shù)組
        vector<int> dp(n + 1);
        // 2.初始化
        dp[0] = dp[1] = 0;
        // 3.填充dp數(shù)組
        for(int i = 2; i <= n; ++i)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        // 4.返回結果
        return dp[n];
    }
};

以下是提交后的結果

解法二

看完解法一之后，我們再來看看解法二

• 首先的話還是一樣，我們要去確定這個 狀態(tài)表示，在解法二中，dp[i]表示的 從i位置出發(fā)，到達樓頂時的最小花費
• 那么接下去就慢慢地推導這個【狀態(tài)轉移方程】，再來回顧一下解法一dp[i]表示為到達i位置時的最小花費

• 那此時我們從i位置出發(fā)也可以分為兩種
  1. 支付當前臺階所需費用，并向后走一步，從i + 1位置到終點
  2. 支付當前臺階所需費用，并向后走二步，從i + 2位置到終點
• 將上面的兩個分析式轉換為公式的話為
  • cost[i] + dp[i + 1]
  • cost[i] + dp[i + 2]

• 那么最后的這個【狀態(tài)轉移方程】即為

dp[i] = min(cost[i] + dp[i + 1], cost[i] + dp[i + 2]);

接下去我們需要考慮的就是這個初始化的問題，首先讀者要清楚的是我們在開這個dp數(shù)組的時候大小應該是多大呢？是n呢，還是n + 1呢？

• 立即揭曉答案：應該是[n]，為什么？原因就在于我們到達n級臺階的時候是不需要支付任何費用的，即dp[n] = 0，所以去開出這個空間也是浪費的，所以這一塊地方應該是作為 樓梯頂部 才對
• 那么從dp[n - 1]到這個頂部的位置所需要支付的費用即為cost[n - 1]，那么從這個dp[n - 2]到這個頂部的位置所需要支付的費用即為cost[n - 2]

• 接下去我們所需要考慮的就是 填表順序，通過【狀態(tài)轉移方程】很明顯可以看出我們需要先獲取到dp[i + 1]、dp[i + 2]的值，才可以去推導出dp[i]的值，所以我們的填表順序應該是從右往左的才對

• 那最后需要考慮的就是返回值了，在本解法中，我們的dp數(shù)組表示的是 從第i個位置出發(fā)到達樓頂?shù)淖钚』ㄙM
• 因為我們可以選擇從第[0]或第[1]個位置出發(fā)，所有最后的結果就是取這兩個位置所需花費的最小值

以下是代碼：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        // 1.定義dp數(shù)組
        vector<int> dp(n);
        // 2.初始化【防止越界】
        dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
        // 從后往前遍歷
        for(int i = n - 3; i >= 0; --i)
        {
            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
        }
        return min(dp[0], dp[1]);
    }
};

來看看優(yōu)化后的效率

0x05 解碼方法*

力扣91. 解碼方法

最后再來一道壓軸題，本題是力扣里中等難度的題目。AC本題，可以讓你對dp的理解進一步提升

• 首先的話我們來分析一下題目所表示的含義：在題目中會給到一個只包含數(shù)字的非空字符串s，然后要我們去對這個字符串做解碼的操作，規(guī)則如下
  • 'A' -> "1"
  • 'B' -> "2"
  • 'C' -> "3"
  • 'Z' -> "26"
• 根據(jù)上面的解碼規(guī)則我們進一步來看題目要求，因為這個字符串中所包含的不僅僅只有一個數(shù)字，所以在解碼的時候便需要涉及到多種的可能性，最后所需要我們返回的也是解碼方法的總數(shù)

了解了題目的基本規(guī)則后，我們通過分析示例來進一步理解題目

• 首先看到示例1，s = “12”，那我們的解碼方式就有 兩種，一種是“A B”（1，2），一種則是L（12）
• 然后看到示例2，s = “226”，那我們的解碼方式就有 三種，一種是“B B F”（2，2，6），第二種是V F（22,6），第三種呢則是B Z（2，26）
• 然后看到示例3，s = “06”，對于這個而言其實是存在問題的，因為“06”是無法映射到【F】的，只有“6”才可以映射到【F】，所以對于這種并不存在解碼的方式

好，當我們分析完題目中所給到的示例后，就需要通過dp動態(tài)規(guī)劃來解決本題，接下去就是算法原理的講解

• 首先第一步，還一樣定義出一個dp數(shù)組，然后將其狀態(tài)表示出來，這里的dp[i]則表示 以 i 位置為結尾時的解碼方法總數(shù)

• 然后接下去我們就要根據(jù)這個狀態(tài)來推導出狀態(tài)轉移方程。我們通過這個dp數(shù)組來進行觀察分析，此處我們考慮到兩種情況，一個是就對i這個位置去做一個解碼，第二種呢則是i - 1和i這兩個位置去結合，結合完之后再去做解碼的操作

• 那這個時候有同學就會有疑問了，為什么不考慮i + 1這個位置呢？這個的話你就要反上去繼續(xù)看我們所講到的這個狀態(tài)表示了。因為我們考慮的是 以 i 位置為結尾時的解碼種數(shù)，對于后面的情況此時還沒有考慮到，所以呢我們不需要去理會i + 1這個位置

• 此時我們在求解dp數(shù)組的時候就就分為以下兩種情況下：
  1. s[i]去單獨解碼，分為兩種情況，那對于單獨的一個數(shù)其取值就有1 ~ 9的可能性，如果這個數(shù)為0的話則表示解碼失敗
  2. s[i - 1]與s[i]合并去解碼的話，我們就需要去考慮兩個數(shù)了，第一個數(shù)要比10來得大，否則的話就要出現(xiàn)我們上面所講到的06這種情況，第二個數(shù)的話要比26來的小，若二者都滿足這種情況的話，則可以解碼成功；否則的話就表示解碼失敗

• 那我們對i這個位置單獨去做解碼的話，其實就相當于把[0, i - 1]解碼的所有的方案數(shù)后面統(tǒng)一加一個字符就可以了，具體如下圖所示??
• 那我們要去找以i - 1為結尾的解碼總數(shù)就可以表示為dp[i - 1]

• 接下去我們再來考慮第二種情況，即我們要考慮到的是兩位數(shù)合并后的情況，那所需要求解的便是[0, i - 2]這段區(qū)間中的解碼總數(shù)，即dp[i - 2]

以下即為我們分析所得出的【狀態(tài)轉移方程】

接下去我們就來考慮初始化的問題

• 首先要初始化的位置相信讀者在看了這么多道題之后應該很快就能反應過來了，我們在初始化的時候應該去初始化dp[0]和dp[1]這兩個位置的值，對于dp[0]來說，我們是對單個位置上的數(shù)去做一個解碼，那出現(xiàn)的情況也就只有【0】和【1】兩種，數(shù)據(jù)的范圍要在0 ~ 9之間
• 那對于dp[1]來說，我們要對合并的兩數(shù)去做一個解碼，那此時就會存在3種情況
  • [0]即為這二者都不存在的時候
  • [1]即為這二者中只有一者存在的情況
  • [2]即為二者都存在的情況

接下去我們再來看填表順序

• 這一塊很好理解，通過我們的【狀態(tài)轉移方程】可以看出后面的數(shù)依賴于前面的數(shù)，那么遍歷的順序即為從左往右

dp[i] = dp[i - 1] + dp[i - 2]

最后的話是關于返回值這一塊，因為我們要找的是到第 i 個位置的解碼總數(shù)，不過題目給出的是一個字符串，對于字符串的最后一個位置是n - 1，那么我們最后返回的結果dp[i - 1]

?? 由于本題代碼比較得復雜，所以接下去分步驟講解一下

• 首先我們要做的就是創(chuàng)建出dp表

// 創(chuàng)建dp表
int n = s.size();
vector<int> dp(n);

• 接下來要做的就是初始化工作，首先要去做的是初始化dp[0]，還記得我們上面分析的嗎，當這個編碼的范圍在1 ~ 9之間的時候，所以在這里我們可以采取一個邏輯判斷，讓dp[0]只接收當前s[0]這個字符的值不為0的情況

// 初始化dp[0]
dp[0] = (s[0] != '0');

• 接下去呢我們考慮初始化dp[1]，首先考慮到兩數(shù)單獨編碼的情況，若均不為0的話則表示可以進行解碼

// 1.兩數(shù)單獨編碼
if(s[0] != '0' && s[1] != '0')
	dp[1] += 1;

• 接下去的話我們還需考慮兩數(shù)結合的情況，因為這邊給到的是字符串，所以我們在取的時候需要將其- ‘0’轉換為數(shù)字才可以，接下去根據(jù)我們剛才所分析的，去判斷這個數(shù)是否在符合的范圍內，若是的話才表示可以解碼

// 2.兩數(shù)結合
int t = (s[0] - '0') * 10 + s[1] - '0';     // 字符串轉數(shù)字
if(t >= 10 && t <= 26)  
    dp[1] += 1;

• 其后我們才去考慮這個【填表】的事情，因為前兩個位置dp[0]和dp[1]已經做了初始化，所以我們從第3個位置開始即可，然后你就可以發(fā)現(xiàn)這個填表的情況和我們在初始化時的場景非常類似，這里就不細說了

// 填表
for(int i = 2;i < n; ++i)   // 從第三個位置開始遍歷
{
    // 單獨編碼的情況
    if(s[i] != '0') dp[i] += dp[i - 1]; 
    // 兩數(shù)結合的情況
    int t = (s[i - 1] - '0') * 10 + s[i] - '0';
    if(t >= 10 && t <= 26)  dp[i] += dp[i - 2];
}

• 最后的話返回dp[n - 1]即可

return dp[n - 1];

以下是整體的代碼展示：

class Solution {
public:
// 狀態(tài)轉移公式
// dp[i] = dp[i - 1] + dp[i - 2]
    int numDecodings(string s) {
        // 創(chuàng)建dp表
        int n = s.size();
        vector<int> dp(n);

        // 初始化dp[0]
        dp[0] = (s[0] != '0');
        // 處理邊界情況
        if(n == 1)  return dp[0];
        
        // 初始化dp[1]
            // 1.兩數(shù)單獨編碼
        if(s[0] != '0' && s[1] != '0')
                dp[1] += 1;
            // 2.兩數(shù)結合
        int t = (s[0] - '0') * 10 + s[1] - '0';     // 字符串轉數(shù)字
        if(t >= 10 && t <= 26)  
            dp[1] += 1;

        // 填表
        for(int i = 2;i < n; ++i)   // 從第三個位置開始遍歷
        {
            // 單獨編碼的情況
            if(s[i] != '0') dp[i] += dp[i - 1]; 
            // 兩數(shù)結合的情況
            int t = (s[i - 1] - '0') * 10 + s[i] - '0';
            if(t >= 10 && t <= 26)  dp[i] += dp[i - 2];
        }
        return dp[n - 1];
    }
};

以下是執(zhí)行結果

四、總結與提煉

最后來總結一下本文所學習的內容??

• 在本文中，我們學習到了大廠面試中非常喜歡考察一種算法類型叫做【動態(tài)規(guī)劃】，它也是令許多同學望而卻步的絆腳石之一，希望在閱讀本文只后可以讓你對dp動態(tài)規(guī)劃有了一個清晰的認識
• 首先我們對動態(tài)規(guī)劃的基礎理論有了一些認識，清楚了什么是 動態(tài)規(guī)劃 以及 動態(tài)規(guī)劃的五部曲
• 之后呢我們就展開對習題的講解和分析，從最基礎的【斐波那契數(shù)】開始，一直到較為復雜的【解碼問題】，隨著一步步地深入，不知讀者是否對動態(tài)規(guī)劃有了進一步的認識

以上就是本文所要介紹的所有內容，感謝您的閱讀??文章來源地址http://www.zghlxwxcb.cn/news/detail-725903.html

到了這里，關于【算法】一文帶你從淺至深入門dp動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！