本文中的題目均來自力扣，代碼默認以C#實現，偽代碼僅用來幫助描述，不嚴格遵循某種語言的語法。
本章中是一些經典的動態規劃面試問題。
我們推薦以下題目：爬樓梯，買賣股票最佳時機 和 最大子序和。
難度：簡單
假設你正在爬樓梯。需要 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 階
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;
}
難度：簡單
給定一個數組，它的第 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;
}
難度：簡單
給定一個整數數組
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;
}
