动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
下面我们通过具体的问题去学习应用动态规划。
问题描述：
有一个小孩上楼梯，共有N阶楼梯，小孩一次可以上1阶或2阶。走到N阶楼梯，一共有多少种走法？
问题分析：
自顶向下分析方式：
爬到第N阶楼梯，一共只有2种情况(全划分，加法原理)，第一种是从第N-1阶爬1阶楼梯到第N阶；第二种是从第N-2阶爬2阶楼梯到第N阶。
故可得到：way(N)=way(N-1)+way(N-2)
下面用Python实现形如Fib数列的问题，代码如下：
# 动态规划 先解决小数据量的 再层层递推的解决大数据量级的问题 时间复杂度O(n) def fib2(n): memo = [-1 for x in range(n+1)] memo[0] = 0 memo[1] = 1 for i in range(2, n+1): memo[i] = memo[i - 1] + memo[i - 2] return memo[n] if __name__ == '__main__': n = 10 print(fib2(n))输出结果如下：
问题描述：
假如有一天老板给你安排了一系列任务供你选择，每个任务的收益是不同的，并且在选择了一个任务之后，在该任务所执行的时间段内不能选择其他任务，也就是所选择的任务时间不能有冲突，这时你该如何去选择任务，可以使你的收益达到最大？假如任务安排如下图所示，红色数字代表每个任务的收益：
问题分析：
对于每一个任务只有两种情况，选择或者不选它。试着倒着分析该问题，选择第8个任务时，就还可以选择第5个任务，最大收益就是他俩的收益和；或者不选择第5个任务，可以选择第4个任务，然后再选择第1个任务，他俩也可以不选择，又是另外的情况。不选择第8个任务时，选择第7个任务，再选择后面的任务；也可能不选择第7 个而选择第6个……
那么可以作如下总结：
i 表示第i个任务，opt表示最大收益，表示第i个任务的收益，prev[i]表示第i个任务之前可以执行的任务。
当选择第 i 个任务时，最大收益为：
当不选择第 i 个任务时，最大收益为：
可以总结出下表：
iprev[i]opt[i]10520530841950962973108513
下面我们以该例子为例用Python实现任务安排问题，代码如下：
# 数组arr存储的是每个任务的收益； arr = [0, 5, 1, 8, 4, 6, 3, 2, 4] #数组prev存储的是指定任务之前可以执行的任务 prev = [0, 0, 0, 0, 1, 0, 2, 3, 5] def dp_opt(arr): #计算任务的长度 len_arr = len(arr) # 存储执行到每个任务可以获得的最优解; opt = [0 for i in range(len_arr)] opt[0] = 0 opt[1] = arr[1] for i in range(2, len(arr)): # 不选择做这个任务的最优解； A = opt[i - 1] # 选择做这个任务的最优解； B = arr[i] + opt[prev[i]] opt[i] = max(A, B) return opt[-1] print(dp_opt(arr))输出结果为最大收益，如下：
问题描述：
给定数组A=[1,2,4,1,7,8,3]，求出数组A中互不相邻的数的最大和。 例如：如果选择了8，则不能选择7和3，在本例中最大的和为1+4+7+3=15
问题关键：不能选相邻的数字 选择的数字和最大max
该问题分析同上面的任务安排问题分析，也可做出类似的总结：
i 为所选择的数字的索引值，那么，
当选择第 i 个数字时，最大和为：
当不选择第 i 个数字时，最大和为：
以该例子为例用Python实现不相邻数最大和问题，代码如下：
arr = [1, 2, 4, 1, 7, 8, 3] def max_sum(arr): len_arr = len(arr) opt = [0 for i in range(len_arr)] opt[0] = 1 opt[1] = arr[1] for i in range(2, len(arr)): not_choice = opt[i - 1] choice = arr[i] + opt[i - 2] opt[i] = max(not_choice, choice) return opt[-1] print(max_sum(arr))输出为计算的最大的和，结果为：
