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

動態(tài)規(guī)劃是一種解決問題的算法思想。它通常用于優(yōu)化問題，其中要求找到一個最優(yōu)解或最大化（最小化）某個目標(biāo)函數(shù)。

動態(tài)規(guī)劃的核心思想是將問題分解成更小的子問題，并通過存儲子問題的解來避免重復(fù)計算。這樣，可以通過解決子問題來構(gòu)建原始問題的解。動態(tài)規(guī)劃通常適用于具有重疊子問題和最優(yōu)子結(jié)構(gòu)特性的問題。

動態(tài)規(guī)劃的一般步驟如下：

1. 確定dp數(shù)組以及下標(biāo)的含義
2. 確定遞推公式
3. dp數(shù)組初始化
4. 確定遍歷順序
5. 舉例推導(dǎo)dp數(shù)組

動態(tài)規(guī)劃與數(shù)學(xué)歸納法的異同：

509. 斐波那契數(shù)

題目鏈接：509. 斐波那契數(shù)

class Solution {
public:
    int fib(int n) {
        vector<int> dp{0, 1};
        dp.resize(n + 1);
        for (int i = 2; i < n + 1; ++i) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp.back();
    }
};

根據(jù)公式 $F(n)=F(n?1)+F(n?2)$，本題其實只需要維護兩個變量就可以求出，稱之為滾動數(shù)組

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        int val1 = 0, val2 = 1;
        while(n-- >= 2) {
            int sum = val2 + val1;
            val1 = val2;
            val2 = sum;
        }
        return val2;
    }
};

動態(tài)規(guī)劃中的滾動數(shù)組是一種空間優(yōu)化技巧，通常用于解決空間復(fù)雜度較高的動態(tài)規(guī)劃問題。滾動數(shù)組通過使用一維數(shù)組來代替二維數(shù)組的一部分或全部，從而減少空間復(fù)雜度。在動態(tài)規(guī)劃的遞推過程中，每一個狀態(tài)只與之前的一個或幾個狀態(tài)有關(guān)，因此只需要用一維數(shù)組來保存這些狀態(tài)的值，而不需要用二維數(shù)組保存所有狀態(tài)值。當(dāng)計算完當(dāng)前狀態(tài)后，可以覆蓋掉前面的狀態(tài)值，從而實現(xiàn)滾動數(shù)組的效果。

例如，求解斐波那契數(shù)列的動態(tài)規(guī)劃實現(xiàn)通常使用滾動數(shù)組。在計算當(dāng)前狀態(tài)值時，只需要用兩個變量來分別保存前兩個狀態(tài)的值，而不需要使用一個數(shù)組來保存所有狀態(tài)值。每次計算完當(dāng)前狀態(tài)值后，將保存前一個狀態(tài)值的變量的值更新為當(dāng)前狀態(tài)值，將保存前兩個狀態(tài)值的變量的值更新為保存前一個狀態(tài)值的變量的值，即可實現(xiàn)滾動數(shù)組。

使用滾動數(shù)組可以大大減少動態(tài)規(guī)劃算法的空間復(fù)雜度，但同時也可能會影響程序的可讀性和可維護性，因為使用滾動數(shù)組通常需要更多的變量和復(fù)雜的變量更新操作。因此，在使用滾動數(shù)組時需要權(quán)衡空間和時間復(fù)雜度與程序可讀性和可維護性之間的關(guān)系，選擇最優(yōu)的算法實現(xiàn)方式。

70. 爬樓梯

題目鏈接：70. 爬樓梯
1個臺階，有1種方法；2個臺階，有2種方法；3個臺階，有1+2種方法。

3個臺階就是1個臺階和2個臺階的總和。為什么？因為題目就讓邁1個或2個臺階，因此到3階，從1階邁兩步，從2階邁一步，因此是1階和2階的總和。這就是將問題分解成更小的子問題，并通過存儲子問題的解來避免重復(fù)計算

同理，4個臺階，通過3階邁一步，2階邁兩步，有2+3種方法。
… …

dp 數(shù)組的含義：到達第 i 階，有 dp[i] 種方法
遞推公式：dp[i] = dp[i -1] + dp[i - 2]
初始化：dp[1] = 1; dp[2] = 2（dp[0]沒有意義，但是為了滿足遞推公式，可以初始化為1）
遍歷順序：從前向后

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp{1, 1, 2};
        dp.resize(n + 1);
        for (int i = 3; i < n + 1; ++i) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp.back();
    }
};

當(dāng)然，因為是斐波那契數(shù)列，也可以維護只兩個變量來完成。

746. 使用最小花費爬樓梯

題目鏈接：746. 使用最小花費爬樓梯
dp 數(shù)組的含義：到達第 i 階，所需要的花費為 dp[i]
遞推公式：dp[i] = min(dp[i -1] + cost[i - 1], dp[i - 2] + cost[i - 2])
初始化：根據(jù)題意可知，dp[0] = 0; dp[1] = 0
遍歷順序：從前向后文章來源地址http://www.zghlxwxcb.cn/news/detail-487664.html

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp{0, 0};
        dp.resize(cost.size() + 1);
        for (int i = 2; i < cost.size() + 1; ++i) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp.back();
    }
};

到了這里，關(guān)于算法Day38 | 動態(tài)規(guī)劃，509. 斐波那契數(shù)， 70. 爬樓梯， 746. 使用最小花費爬樓梯的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！