“动态规划总结”
何为动态规划
动态规划 wiki，首先明确适合用动态规划来解决问题的情况：
- 问题存在最优子结构，问题最优解中子问题的解也是子问题的最优解。
- 子问题最优解无后效性，子问题的最优解不会随着求解问题规模的扩大而改变。
- 子问题存在重叠，由问题分解出的很多子问题中，存在一部分相同的子问题，这意味着我们可以存储好这一部分子问题的结果，避免重复计算。
在分析问题时可以先用该三点来检验问题是否可用动态规划求解。
动态规划例题
刷LEETCODE的时候经常会碰到动态规划的题目，动态规划最重要一点是找到其内含的递推关系，有的时候需要记录多个状态的值，有的时候只需要记录仅有的几个状态的值，这些都视递推关系而定。
热身
菲波那切数列，这个经常被用于讲解递归的初始小案例，其实也是个经典的动态规划问题，简单的动态规划问题最终要的就是要找到递推关系。比如斐波那契数列的递推关系就很明显。
菲波那切数列数列：
1,1,2,3,4,5,13,21 ...
fib(n) = fib(n-1) + fib(n-2)
可见，要求fib(n)需要求出fib(n-1)和fib(n-2)，递推关系一直延伸到n = 3的时候。我们每次只要存储 fib(n-1)的值和fib(n-2)的值就行了。
第二个案例
假如有8项任务，其中每个任务都有起始时间以及得到的报酬。现在给出8项任务的时间特点，求选做那几项，最后得到的报酬最多。下面是8项任务的具体细节：
编号，时间段，报酬
1. 1-4,5
2. 3-5,1
3. 0-6,8
4. 4-7,4
5. 3-8,6
6. 5-9,3
7. 6-10,2
8. 8-11,4
推导的方法就是分析两种状态，选和不选。 首先假设 opt(i) 表示在考虑第 i 任务，选和不选的最大报酬。 从 opt(8)开始分析：
- 选： 4 + opt(5)
- 不选： opt(7) 选二者中的最大值，就是得到的最大报酬。 这样问题就递推到了 opt(5) 和 opt(7)。
最终会递推到第1个任务。
再做每道动态规划题的时候，要始终有不惜多开空间来保存各种信息的觉悟，题目理顺了之后，可以再根据题目的特点，分析到底是需要多少空间，再节省空间，当然这是我这个新手的体会。
对于这道题目，可以开辟一个数组opt数组表示当考虑到第 i 个任务的时候，最优选择下的最大报酬。
一般初始的几个状态是不能使用递推关系的，需要做特别的分析。之后一直推移到可以用递推关系时，再使用即可。
198. House Robber(LEETCODE)
该题的递推关系为：
t[n] = max(t[n-1],nums[n]+t[n-2])
相应代码：
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums)
prepre = nums[0]
pre = max(nums[0:2])
i = 2
while(i<len(nums)):
tmp = max(pre,prepre+nums[i])
prepre = pre
pre = tmp
i += 1
return max([pre,prepre])
70. Climbing Stairs
该题目的递推关系：
s[n] = s[n-1] + s[n-2]
代码：
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
if n == 2:
return 2
pre = 2
prepre = 1
ren = 0
for i in range(3,n+1):
ren = pre + prepre
prepre = pre
pre = ren
return ren
322. Coin Change
这道题目说的是，给定一些面值的硬币，并且能够无限供应。给定一个数额，求能够达到这个数额的最小的硬币数。该题目的递推关系:
s[i] = min(1 + s[i - c[k]]) # 其中 1 是指从 s[i - c[k]] 状态到 s[i] 状态所添加的那一枚硬币，c[k] 是指第 k 枚硬币的面值
代码：
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
# 创建一个长度为 amount的数组
if amount == 0:
return 0
if amount in coins:
return 1
flag = [-1] * ( amount + 1 )
for c in coins:
if c < amount:
flag[c] = 1
for i in xrange( 1 , amount):
if flag[i] != -1:
for c in coins:
if c + i <= amount:
if flag[c + i] == -1:
flag[c + i] = flag[i] + 1
elif flag[c + i] > flag[i] + 1:
flag[c + i] = flag[i] + 1
return flag[amount]
53. Maximum Subarray
题目地址 这道题目的特别之处在于其最终结果并非存在于递推公式中, 该题目的递推公式为
# i = 0 或 f(i-1) <= 0
f(i) = nums[i]
# f(i-1) > 0 且 i != 0
f(i) = f(i-1) + nums[i]
在分析该问题时，硬要将求解结果表示在递推公式中，结果总是找不到合适的递推公式，了解了该递推公式后，发现在此处需要扩展思路，递推公式中不一定包含最终的求解结果。像本题中，f(i) 表示的是某一段子数组的和，而问题求解的最终结果却是 max(f(i))。
具体代码如下
class Solution {
public int maxSubArray(int[] nums) {
int curSum = 0;
int maxSum = Integer.MIN_VALUE;
for(int i = 0;i< nums.length;i++){
if(curSum < 0)
curSum = nums[i];
else{
curSum += nums[i];
}
if(curSum > maxSum)
maxSum = curSum;
}
return maxSum;
}
}
