力扣初級演算法（六）【動態規劃】

本文中的題目均來自力扣，代碼默認以C#實作，偽代碼僅用來幫助描述，不嚴格遵循某種語言的語法，

本章中是一些經典的動態規劃面試問題，

我們推薦以下題目：爬樓梯，買賣股票最佳時機和最大子序和，

力扣初級演算法（六）【動態規劃】
- 70. 爬樓梯
  - 解題思路
    - 方法一：遞回
    - 方法二：記憶化遞回
    - 方法三：動態規劃
    - 方法四：空間壓縮
- 121. 買賣股票的最佳時機
  - 解題思路
    - 方法一：遞回
    - 方法二：記憶化遞回
    - 方法三：動態規劃
    - 方法四：空間壓縮
- 53. 最大子序和
  - 解題思路
    - 方法一：動態規劃
    - 方法二：狀態壓縮
- 最后

70. 爬樓梯

難度：簡單

假設你正在爬樓梯，需要 n 階你才能到達樓頂，

每次你可以爬 1 或 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數，

示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂，
1.  1 階 + 1 階
2.  2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂，
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階

解題思路

樸素的想法是，窮舉所有的肯能，這在問題規模比較小的時候，是可行的，但當問題規模擴大的時候，我們似乎沒有辦法一次性列舉所有的可能，
稍加思考，我們觀察一些題目，看看一個較大規模的問題的答案能否根據一些較小規模的問題求得，
我們每次可以爬1個或者2個臺階，也就是說，在每一層臺階上，我都有兩種選擇，
但是當我即將到達樓頂的時候，比如說我現在第八個臺階上，樓頂在第九個臺階上，我只能選擇爬一個臺階，
那么到達第十個臺階的方案，是不是就是在到達第九個臺階的方案的基礎上全部選擇再爬一個臺階呢？
除此之外，我還有沒有其他可能的選擇到達第十個臺階呢？
- 我是不是可以在第八個臺階上選擇一次性上兩個臺階，也可以在第九個臺階上選擇上一個臺階呢？
- 答案似乎已經出來了，我們只需要知道有多少中到達和比八個臺階的方案，和多少種到達第九個臺階的方案，就能知道有多少個到達第十個臺階的方案，
- 值得注意的是，在第八個臺階上，我們可以選擇兩次爬一個臺階到達樓頂，但這種情況已經被包含在到達第九個臺階的方案當中了，所以不必重復計算，
我們可以采用遞回的寫法，把問題不斷拋出，直到達到一個較小的規模，
- 這里我們把0個臺階的方案也視為一種，因為我們已經在樓頂了，沒有其他的選擇，

方法一：遞回

public int ClimbStairs(int n)
{
    if (n == 0 || n== 1) return 1;

    return ClimbStairs(n - 1) + ClimbStairs(n - 2);
}

遞回的寫法很簡單，但這是一個好的解決方案嗎？
和我們之前寫的遞回不同，這次我們將一個問題變成了兩個問題，隨著問題規模的擴大，我們會拋出越來越多的問題，而且這些問題中有相當一部分是重復的，
- 比如，在計算到達第十個臺階的方案當中，我們先計算了到達第八個臺階和第九個臺階的方案，而在計算到達第九個臺階的方案中，我們計算了到達第八個臺階和到達第七個臺階的方案，
我們不想做這些重復的計算，那么有沒有辦法優化一下呢？我們可以不可以記錄一下我們解決過的問題，當我們遇到相同的問題的時候，直接拿答案就好了，沒必要進行重復計算，

方法二：記憶化遞回

private static Dictionary<int, int> dp = new Dictionary<int, int>();

public int ClimbStairs(int n)
{
    if (n == 0 || n == 1) return 1;

    return dp.ContainsKey(n)? dp [n]: dp[n] = ClimbStairs(n - 1) + ClimbStairs(n - 2);
}

我們可以看出，遞回本質上是從一個大規模的問題開始，找到一個較小規模的問題，然后利用這個較小規模問題的答案，進一步計算大規模問題的答案，在回歸的程序中，一步一步計算問題的答案，只找到最終解決目標問題，
那么我們可不可以一開始就從最小規模的問題開始計算呢？

方法三：動態規劃

public int ClimbStairs(int n)
{
    var dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i < dp.Length; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

既然到達第十個臺階只需要知道到達第八個臺階和第九個臺階的方案即可，那么我們還有必要存盤第七個臺階和之前的方案嗎？
顯然，我們可以在空間上也進行一定程度的優化，

方法四：空間壓縮

public int ClimbStairs(int n)
{
    int a = 1;
    int b = 1;

    for (int i = 2; i <= n; i++)
    {
        (b, a) = (a + b, b);
    }

    return b;
}

121. 買賣股票的最佳時機

難度：簡單

給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，

如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設計一個演算法來計算你所能獲取的最大利潤，

注意：你不能在買入股票前賣出股票，

示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 ，
     注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票，
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0，

解題思路

樸素的想法是，窮舉所有的可能情況，我們在每一天都嘗試買入，在之后的每一天都嘗試賣出，最后得到一個最大值，
顯然，這在問題規模比較大的時候，并不是一個好的方案，我們可否像之前一樣對問題進行拆分呢？
由于只能買賣一次，我們要想利潤最大化，必然需要在歷史最低點買入，最高點賣出，
我們可以把問題拆分成，每天都嘗試賣出，只不過買入的點均為相對于今天的歷史最低點，因為我們還不知道明天會是怎樣，
最后，找到賣出利潤的最大值即可，

方法一：遞回

public int MaxProfit(int[] prices)
{
    return MaxProfit(prices.Length - 1);

    int MaxProfit(int day)
    {
        if (day <= 0) return 0; // 遞回的終點

        var last = MaxProfit(day - 1);
        var today = prices[day] - prices.Take(day).Min(); // 今天-歷史最低
        return Math.Max(last, today);
    }
}

在上面的方法中，我們每天都計算了一次歷史最低值，顯然，這一部分中有大量的重復計算，我們可以用一個遍歷來維護這個歷史最低值，

方法二：記憶化遞回

public int MaxProfit(int[] prices)
{
    if (prices.Length < 1) return 0;
    int min = prices[0];

    return MaxProfit(prices.Length - 1);

    int MaxProfit(int day)
    {
        if (day <= 0) return 0;

        var last = MaxProfit(day - 1);
        min = Math.Min(prices[day - 1], min);
        var today = prices[day] - min;

        return Math.Max(last, today);
    }
}

換個角度思考一些問題，回歸到選擇上面，我們每天是不是都有兩個選擇呢？

買入或者賣出，
由于只能買賣一次，所以在買入之前，我們不能賣出，在賣出之后，我們不能買入也不能賣出，
為了方便描述，我們可以定義如下幾個狀態：
- 觀望狀態
- 已買入狀態
- 已賣出狀態
一開始，我們處于觀望狀態，我么不知道要在哪天買入，所以先觀望一下，
樸素的想法是，要是可以存檔就好了，我們可以在今天分別選擇買入或者賣出，存兩個檔，一旦我后悔了，就可以快速讀檔重新來過，
我們新建一個存檔庫，就叫做DP好了，
- 我們是不是每一天都需要存兩個檔呢？表示今天買入了或者今天賣出了，
```
DP[i][0] 已買入 DP[i][1] 已賣出 i表示天數
```
- 那么我存檔中存什么資料呢？直觀的想法是，存放我們身上持有的資金好了，畢竟最終要求利潤最大化，那身上的錢自然是越多越好，
- 在第一天，我們只能選擇買入，故
```
DP[0][0] = -prices[0] // 起始資金為0，空手套白狼
DP[0][1] = 0 // 還沒買入，不能賣出，身上一分錢都沒
```
- 在第二天，我們可以選擇買入和賣出了，如果買入，那昨天必然沒有買入，如果賣出，昨天必然已經買入，
```
DP[1][0] = -prices[1] // 還是空手套白狼
DP[1][1] = prices[1] + DP[0][0] // 賣出獲得的錢 + 加上之前欠下的錢
```
- 稍加思考，我們肯定不能每天都買入，要進行一定的判斷，如果今天買入的價格比昨天還高，那我為什么不昨天買？
```
DP[1][0] = Max(DP[0][0], -prices[1]) // 昨天買入和今天買入
```
  如果我昨天賣了得到的錢更多，那我為什么不昨天就賣了？反正我是有存檔的人，哪天想賣就哪天賣，
```
DP[1][1] = Max(prices[1] + DP[0][0], DP[0][1]) // 昨天賣出和今天賣出
```
- 以此類推，我們可以存完每一天的檔，最后一天結束的時候，我們賣出的那個檔案一定就是最大利潤，

方法三：動態規劃

public int MaxProfit(int[] prices)
{

    if (prices.Length < 1) return 0;

    var dp = new int[prices.Length, 2]; // 0已買入，1已賣出
    dp[0, 0] = -prices[0];

    for (int i = 1; i < prices.Length; i++)
    {
        dp[i, 0] = Math.Max(dp[i - 1, 0], -prices[i]); // 昨天買入和今天買入對比
        dp[i, 1] = Math.Max(prices[i] + dp[i - 1, 0], dp[i - 1, 1]); // 昨天賣出和今天賣出對比
    }

    return dp[prices.Length - 1, 1];
}

實際上，你已經發現，我們所謂的存檔，其實也是記錄了一個歷史最低值，我們在這個時機買入，在每天都嘗試賣出，由于我們只記錄一個歷史最低值和利潤最大值，完全可以不用存那么多檔，用兩個變數分別記錄一下就好，

方法四：空間壓縮

public int MaxProfit(int[] prices)
{
    if (prices.Length < 1) return 0;

    var min = prices[0];
    var max = 0;

    for (int i = 1; i < prices.Length; i++)
    {
        if (prices[i] - min > max) max = prices[i] - min;
        if (prices[i] < min) min = prices[i];
    }

    return max;
}

53. 最大子序和

難度：簡單

給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，

示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子陣列 [4,-1,2,1] 的和最大，為 6，
進階:

如果你已經實作復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解，

解題思路

樸素的想法是，窮舉所有的可能，從每一個元素開始，尋找連續子陣列最大和，
顯然，我們有更好的辦法來解決這個問題，經過前兩題的操練，我們自然而然的會去嘗試動態規劃的解法，
對于陣列中的每一個元素，我們都有兩個選擇，拿或者不拿，
由于題目要求連續子陣列，我們選擇拿或者不拿會收到一定限制，為了便與描述，我們定義如下狀態：
- 觀望狀態，此時可以選擇拿或者繼續觀望
- 拿，此時可以選擇繼續拿，或者不拿，
- 不拿，直到結束，我們都不能再拿，
一開始，我們處于觀望狀態，這和之前的股票問題有點相似，而且同樣都是只能"買賣"一次，

我們依舊可以每天存兩個檔，0表示不拿，1表示拿，分別記錄手中的元素和，

DP[0][0] = int.MinValue; // 不拿，手中元素和為最小值
DP[0][1] = nums[0]; // 拿了，值為手中元素和，

第二個元素

DP[1][0] = Max(DP[0][0], DP[0][1]) // 終止了，從昨天的檔案中選一個最大值
DP[1][1] = Max(DP[0][1] + nums[1], nums[1]) // 接著拿，或者之前在觀望，今天開始拿

以此類推，最后我們選擇最后一天的存檔中，較大的那一個即可，

方法一：動態規劃

public int MaxSubArray(int[] nums)
{
    var dp = new int[nums.Length, 2]; // 0 不拿 1 拿
    dp[0, 0] = int.MinValue;
    dp[0, 1] = nums[0];

    for (int i = 1; i < nums.Length; i++)
    {
        dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i - 1, 1]);
        dp[i, 1] = Math.Max(dp[i - 1, 1] + nums[i], nums[i]);
    }

    return Math.Max(dp[nums.Length - 1, 0], dp[nums.Length - 1, 1]);
}

很快，我們發現，今天的存檔只取決于前一天的存檔，我們依舊可以在空間上進行壓縮，

方法二：狀態壓縮

public int MaxSubArray(int[] nums)
{
    var sum = 0;
    var max = nums[0];

    foreach (var item in nums)
    {
        sum = Math.Max(sum + item,item); // 連續和 和 只拿今天的
        max = Math.Max(sum, max);// 當前連續和 和 歷史最大和
    }

    return max;
}

最后

回顧動態規劃的一系列問題，實際上就是從我們暴力列舉的辦法中優化掉重復的計算和不必要的空間，
除了動態規劃的解法之外，本篇中的三道題目都有其他的解法，感興趣的讀者可以思考嘗試一下，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/184378.html

標籤：其他

上一篇：Azure 解決方案：淺談聯合身份驗證

下一篇：Azure 解決方案：將本地Windows Server AD 賬戶與Azure AD集成