一、吃烧饼（动态规划）
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)