一、吃燒餅（動态規劃）
1. 題幹
吃燒餅，有n個盤子和每個盤子的燒餅數，每次選一個x(x <= n)，吃掉第1x号盤子的一個燒餅，若第1x号盤子中有空盤，則不能選擇這個x。 假設胃無限大，問最多可以吃多少燒餅。
2、樣例
輸入
3
2 1 3
輸出：
4
3、解題分析
狀态定義：設dp[i]是第i個盤子中最多能吃到的燒餅的數量（那麼每個盤子最多能吃到的餅的數量之和就是傳回結果）
轉移方程：如果第dp[i]個盤子中的燒餅數量比dp[i-1]中的燒餅數量多，那麼第i個盤子中隻能吃掉和dp[i-1]相等數量的燒餅；反之，可以把第i個盤子中的燒餅吃光；
dp[i] = min(dp[i-1], dp[i])
初始狀态：如果隻有一個盤子，那麼顯然可以全部吃光，即dp[0] = nums[0]
傳回值：狀态轉移清單中所有值之和。
4、python代碼
(1)方法一：
def f(nums):
for i in range(1, len(nums)):
nums[i] = min(nums[i-1], nums[i])
return sum(nums)
以執行個體舉例說明狀态轉移清單中的數值變化：
（2）方法二：
def f(nums):
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = min(nums[i-1], nums[i]) + dp[i-1]
return dp[-1]
5、複雜度分析
方法一：
（1）時間複雜度：周遊所有樣本，時間複雜度為O(n)
（2）空間複雜度：沒有占用額外的存儲空間，空間複雜的為O(1)
方法二：
（1）時間複雜度：周遊所有樣本，時間複雜度為O(n)
（2）空間複雜度：占用額外的存儲空間dp，空間複雜的為O(n)