动态规划（Dynamic Programming）
从分治到动态规划：动态规划的基本思想是将待求解的问题分解为若干个子问题，这与分治的思想类似，
不同的地方在于当子问题之间是相互独立的，这时候分治算法是我们解决问题的最好的思路，因为不同的子问题求解不会有公共的重复计算的地方，然而，当分解得到的子问题不相互独立时，动态规划就是我们最好的选择，我们可以建立一个cache来记录重复计算的部分，从而避免重复计算。后面会讲到这会使得一个多项式级别的问题变为线性的时间
关键点：找子问题，如果一个问题具有无后效性，即后面的结果不会对前面的结果再次产生影响，可以选择使用动态规划。然而后面问题解的更改会倒置前面最优解发生变化，比如：下围棋，等策略游戏的编程就无法使用动态规划，一般采取回溯算法。
状态转移方程：这是动态规划的核心，一般找出前面状态的最优解和当前状态最优解的关系即为状态转移方程。例如：最大子数组问题，我们可以找出前面以所有位置为结尾的最大子数组，随后求出最大的作为结果；再比如：买股票，我们可以建模为：dp[i] 表示第i天将股票卖出可以获得的最大利润，从而求得取所有子结果最大值作为全局最优；再比如：爬楼梯问题我们可以建模为 dp[i] = dp[i - 1] + dp[i - 2]表示第i次我可以选择爬一层或者爬两层来决定全局方案总数。
使用场景：一般的对于一个算法问题，我们首先可以暴力求解，观察他的复杂度，如果这个复杂度是k^n复杂度，可以考虑优化为O(nk)这时候一般会采取建立k维动态矩阵求解。
可实施性：一般的对于k^n都的复杂度算法都可以看成当前状态和前面k个状态有关，于是我们可以采用递归的方式（top down），然而这样会导致下面的某个节点会被重复计算很多次，因为上方父节点会用到，每用到一次，下方节点就需要重新计算一次，于是我们可以采用建立缓存记录计算过的值或者就是我们所说的动态数组(bottom up)避免重复计算，从而大大地优化了时间复杂度。举例：斐波那契额数列通项式f(n) = f(n - 1) + f(n - 2)如果我们采用递归的方式解决，会是O(2^n)的复杂度，因为递归采取的是从f(n)计算到f(1), f(2)，回溯到f(n)，而我们采用动态数组``dp[i] = dp[i - 1] + dp[i - 2]即从前向后则可以使得前面的值得以记录。复杂度降为O(n)`
一维动规优化
优化点：空间的优化，因为大多数问题我们通过动态方程可以看出，当前状态只与前面的一个或者俩个状态决定。如题目中所说三个问题: maxSubarray:dp[i] = max(dp[i - 1] + nums[i], nums[i])；sell stock: dp[i] = max(dp[i - 1] + nums[i] - nums[i - 1], 0);Climbing Stairs: dp[i] = dp[i - 1] + dp[i - 2]。观察这三个动态方程我们发现当前状态都是只与dp[i - 1]或者 dp[i - 2]有关。于是我们可以考虑用指针来记录前面的两个或一个状态点的值，从而完成当前状态的计算。而不需要取申请数组。下面给出三个问题的原版和优化版的解决方案：
- maxSubarray:
题目：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
常规数组解法O(n)空间：
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
优化为O(1)空间：
import sys
class Solution(object):
def maxSubArray(self, nums):
res = -sys.maxint
pre = 0
for i in nums:
if pre <= 0:
pre = i
res = max(res, pre)
else:
pre = pre + i
res = max(res, pre)
return res
- Climbing Stairs:
题目：
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
常规数组解法O(n)空间：
# Bottom up, O(n) space
def climbStairs2(self, n):
if n == 1:
return 1
res = [0 for i in xrange(n)]
res[0], res[1] = 1, 2
for i in xrange(2, n):
res[i] = res[i-1] + res[i-2]
return res[-1]
优化为O(1)空间：
class Solution(object):
def climbStairs(self, n):
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
pre = 2
prepre = 1
for i in xrange(n - 2):
tmp = pre + prepre
prepre = pre
pre = tmp
return pre
- sell stock
题目：
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
O(n)空间的思路可以读者自己写，给出O(1)的思路
import sys
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
n = len(prices)
if n <= 1:
return 0
res = 0
minP = prices[0]
for i in xrange(1, n):
res = max(res, prices[i] - minP)
minP = min(prices[i], minP)
return res
下期分析不能进行空间优化的一维动态规划。有不足的地方请指正
转载著名出处：http://www.jianshu.com/p/62e54802d12c
