通過查閱相關(guān)資料發(fā)現(xiàn)動態(tài)規(guī)劃問題一般就是求解最值問題。這種方法在解決一些問題時應(yīng)用比較多，比如求最長遞增子序列等。

有部分人認為動態(tài)規(guī)劃的核心就是：窮舉。因為要求最值，肯定要把所有可行的答案窮舉出來，然后在其中找最值。

首先，筆者認為動態(tài)規(guī)劃中的窮舉有一定的特點，因為這類問題有重疊的子問題存在，暴力窮舉效率極其低下，所以需要“備忘錄（DP Table）”優(yōu)化窮舉過程，從而盡可能的避免不必要的計算。其次，動態(tài)規(guī)劃問題一定有“最優(yōu)子結(jié)構(gòu)”，只有這樣才能通過子問題的最值得到原問題的最值。另外，窮舉所有可行解通常較為困難，只有列出正確的“狀態(tài)轉(zhuǎn)移方程”才能正確地窮舉。

上述的重疊子問題、最優(yōu)子結(jié)構(gòu)、狀態(tài)轉(zhuǎn)移方程就是動態(tài)規(guī)劃三要素。在實際應(yīng)用中寫出狀態(tài)轉(zhuǎn)移方程是最困難的。通常根據(jù) “明確問題狀態(tài)?-> 定義 dp 數(shù)組/函數(shù)的具體含義 -> 明確轉(zhuǎn)移 -> 明確基本實例” 來構(gòu)建狀態(tài)轉(zhuǎn)移方程。

最長遞增子序列 LeetCode#300

dp[i] 表示當(dāng)最后一個數(shù)值為 nums[i] 時，此時對應(yīng)的最長遞增子序列的長度是 dp[i]。在下述例子中當(dāng) i=2 時 dp[2] 表示當(dāng)最后一個數(shù)為 3 時，對于數(shù)組 {1, 4, 3} 中最長遞增子序列的長度 dp[2]=2。

基于動態(tài)規(guī)劃理論，當(dāng)已知前面第 i - 1 個值時，可以利用下述代碼求解得到第 i?個值。

for (int j = 0; j < i; j++) {
    if (nums[j] < nums[i]) {
        dp[i] = max(dp[i], dp[j] + 1);
    }
}

當(dāng)?shù)玫?dp 數(shù)組后，只需要求得 dp 數(shù)組的最大值（即為最大遞增子序列的長度）即可。

int ret = 1;
for (auto it : dp) {
    ret = max(ret, it);
}

普通動態(tài)規(guī)劃算法?O(N^2)

因此可以利用該方法解決 #300 問題，具體代碼如下所示。但是該算法的時間復(fù)雜度為 O(n^2)，這對于較大數(shù)據(jù)量而言，性能不太能接受。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int length = nums.size();
        vector<int> dp(length, 1);
        for (int i = 0; i < length; i++) {
            //對于某一個還未計算的dp[i]，在nums的前i個中找到比nums[i]小的dp[j]，
            //然后進行加1；可能會出現(xiàn)多個滿足的dp[j]，取其中值最大的一個作為最終結(jié)果。
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        //找到dp數(shù)組中的最大值（也就是最長遞增子序列的長度）
        int ret = 1;
        for (auto it : dp) {
            ret = max(ret, it);
        }
        return ret;
    }
};

優(yōu)化動態(tài)規(guī)劃算法 O(NlogN)

對于該方法的具體優(yōu)化可以參考?動態(tài)規(guī)劃設(shè)計之最長遞增子序列

該算法的思路有點像游戲 “空當(dāng)接龍”，也就是對于每一張撲克牌，數(shù)值小的牌只能放在大牌的堆上面，當(dāng)沒有合適的堆時，新建一個堆放置該撲克牌；當(dāng)有多個滿足條件的堆時，將撲克牌放在最左端的堆上面（保證撲克牌堆頂?shù)呐朴行颍?/p>

#define MAX_HEAP 2500
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int heap_top_num[MAX_HEAP];
        int heap_cnt = 0;
        for (auto num : nums) {
            int left = 0;
            //對于每一個 num，區(qū)間右邊的值需要重新設(shè)置初始值。
            int right = heap_cnt;
            while (left < right) {
                int mid = (left + right) >> 1;
                //找到最先大于 num 的堆定元素
                if (heap_top_num[mid] >= num) {
                    right = mid;
                }
                else {
                    left = mid + 1;
                }
            }
            //當(dāng)沒有找到符合條件的 mid 時，退出條件是最右端區(qū)間位置，也就是 heap_cnt。
            //此時需要新建一個數(shù)值堆
            if (left == heap_cnt) {
                heap_cnt++;
            }
            heap_top_num[left] = num;
        }
        //堆的個數(shù)就是最長遞增子序列的長度
        return heap_cnt;
    }
};

轉(zhuǎn)變最長遞增子序列應(yīng)用 LeetCode#354

這道題目需要按照第一維參數(shù)進行升序排序，然后按照第二維參數(shù)降序排序（該維度中找出最長遞增子序列即可）。

注意點對于二維的 vector<vector<int>> 按照用戶自定義排序方式進行排序。

首先按照第一維度進行升序排序，如果第一維度元素相等，則按照第二維度進行降序排序。這里平時寫的重載的邏輯有所不一致，需要特別注意。文章來源地址http://www.zghlxwxcb.cn/news/detail-456891.html

sort(envelopes.begin(), envelopes.end(), 
    [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] > b[1]: a[0] < b[0];
            });

#define MAX_EN 100002
class Solution {
public:
    int heap_top[MAX_EN];
    int max_evlp;
    //利用二分法求解最長遞增子序列的長度。
    int longIncSub(vector<vector<int>>& sorted_subs) {
        for (int i = 0; i < max_evlp; i++) {
            heap_top[i] = 1;
        }

        int sub_cnt = 0;
        for (const auto& evlp : sorted_subs) {
            int left = 0;
            int right = sub_cnt;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (heap_top[mid] >= evlp[1]) {
                    right = mid;
                }
                else {
                    left = mid + 1;
                }
            }

            if (left == sub_cnt) {
                sub_cnt++;
            }
            heap_top[left] = evlp[1];
        }
        return sub_cnt;
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        max_evlp = envelopes.size();
        //對二維vector按照用戶需要的排序規(guī)則進行排序方法。
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] > b[1]: a[0] < b[0];
            });

        return longIncSub(envelopes);
    }
};

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