动态规划与贪心法的关系
基本归纳法：对于，只需要考察前一个状态
即可完成整个推理过程，它的特点是只要状态
确定，则计算
时不需要考察更前序的状态，我们将这一模型称之为马尔科夫模型
高阶归纳法：相应的，对于，需要考察前i个状态集{
}才能完成整个推理过程，往往称之为高阶马尔科夫模型
在计算机算法中，高阶马尔科夫模型的推理，叫做“动态规划”，而马尔科夫模型的推理，对应“贪心法”。
最长递增子序列LIS
给定长度为N的数组A，计算A的最长的单调递增的子序列（不一定连续）
如：给定数组A{5,6,7,1,2,8}，则A的LIS为{5,6,7,8}，长度为4
长度为N的数组记为A={}
记A的前i个字符构成的前缀串为，以
结尾的最长递增子序列记为
，其长度为b[i]；
假定已经计算得到了b[0,1,......,i-1]，如何计算b[i]?
已知的前提下如何求
根据定义，必须以
结尾；
如果将分别缀到
的后面，是否允许呢？
如果，则可以将
缀到
后面，得到比
更长的字符串
从而：
计算b[i]：遍历在i之前的所有位置j，找出满足条件的最大的
计算得到后遍历b[i]，找出最大值即为最大递增子序列的长度。
时间复杂度为
的最长递增子序列算法（贪心法）
对于数组A={1,4,5,2,8,9,7}
将A中的数字依次遍历做压栈操作，当遇到数组中的数字比栈中某个数字大，比某个数字小的情况下，进行替换操作，最后栈中数字个数即为最大递增子序列的长度。
股票最大收益
给定数组A[0......N-1]，其中A[i]表示某股票第i天的价格。如果允许最多只进行一次交易（先买一次，再卖一次），请计算合适买卖达到最大收益，返回最大收益值。
如：[7,1,5,3,6,4]，则最大收益为6-1=5
如：[7,6,4,3,1]，则最大收益为0
一路下跌，则最好的方法是不进行交易。
给定数组A[0......N-1]，其中A[i]表示某股票第i天的价格。如果允许最多只进行K次交易（先买一次，再卖一次，算一次交易），请计算合适买卖达到最大收益，返回最大收益值。
规定买卖不能嵌套，及买入后要先卖出才可再买
如：A=[7,1,5,3,6,4]，k=3，则在1,3处买入，5,6处卖出，最大收益为7
分析：
dp[k,i]表示最多k次交易在第i天的最大收益。
在第i天，有俩种选择：要么卖出股票，要不卖出股票，从而得到状态转移方程。
进一部分析
任务安排
给定一台有m个存储空间的单进程机器，现有n个请求：第i个请求计算时需要占用R[i]个空间，计算完成后，存储计算结果需要占用O[i]个空间（其中O[i]<R[i]）。问如何安排这n个请求的顺序，使得所有请求都能完成。
如：m=14，n=2，R[1,2]=[10,8]，o[1,2]=[5,6]。可以先运行第一个任务，计算时占用10个空间，计算完成后占用5个空间，剩余9个空间执行第二个任务；单如果先运行第二个任务，则计算完成后仅剩余8个空间，第一个任务的计算空间就不够了。
算法分析：
第K个任务的计算占用空间加上前面k-1个任务空间占用量之和，越小越好。从而：
得：将按照R[i]-O[i]降序排列即可
操作最小次数
变量x从1开始变化，规则是：要么变成x+1，要么变成2*x，问：若想将x变成整数2015，最少需要多少次变化？
一种可行的操作变化：
1,2,3,6,7,14,15,30,31,62,124,125,250,251,502,503,1006,1007,2014,2015
如何思考：
任何一个数字都可以，如：20161006
1001100111010000111101110
设dp(n)表示从1到n的最少操作数
若n为奇数，则n的前一步只能是n-1
若n为偶数，则n的前一步是n-1和n/2的操作步数的小者
