在学习动态规划之前，我们首先要知道什么是动态规划？
动态规划与分治方法类似，都是通过组合子问题的解来求解原问题的。再来了解一下什么是分治方法以及两者之间的差别，分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。而动态规划与之相反，动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治方法就会做许多不必要的工作，它会反复求解那些公共子子问题。而动态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解子子问题时都重新计算，避免了不必要的计算工作。
动态规划的方法一般用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值。我们希望找到具有最优值的解，我们称这样的解为问题的一个最优解而不是最优解，因为可能有多个解都达到最优值。
解决动态规划问题一般分为四步：
1、定义一个状态，这是一个最优解的结构特征
2、进行状态递推，得到递推公式
3、进行初始化
4、返回结果
我们通过几个例子来演示动态规划的过程
[编程题]斐波那契数列 热度指数：374145时间限制：1秒空间限制：32768K 算法知识视频讲解 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 这个题目相信大家都很熟悉： 在我们学习递归的时候应该都见过：我们先写一个递归版本的。 代码如下：
class Solution { public: int Fibonacci(int n) { if(n<=0) return 0; if(n == 1 || n == 2) return 1; return Fibonacci(n-1)+Fibonacci(n-2); } };这个代码的时间复杂度是2^n，也就是指数递增，如果求一个很大数字的时候，运行就会出错，造成栈溢出。
下面我们用动态规划来求解这个问题：
def fabonacii_fun(n): if n <= 0: return 0 if n == 1: return 1 fn1 = 0 fn2 = 1 result = 0 for i in range(2, n + 1): result = fn1 + fn2 fn1 = fn2 fn2 = result return result if __name__ == "__main__": print(fabonacii_fun(6))可以对这个代码进行优化，将空间复杂度变为O（1）
[编程题]变态跳台阶 热度指数：221924时间限制：1秒空间限制：32768K 算法知识视频讲解 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 先来看简单分析：
def jumpfloor_fun(n): if n == 0: return 1 if n == 1: return 1 total = 1 for i in range(2, n +1): total = 2 * total return total if __name__ =="__main__": print(jumpfloor_fun(3)) def rectCover_fun(n): if n== 0: return 0 if n==1: return 1 if n ==2: return 2 fn1 = 1 fn2 =2 total = 0 for i in range(3,n +1): total = fn1 + fn2 fn1 = fn2 fn2 = total return total print(rectCover_fun(4))编程题]最大连续数列和 热度指数：5518时间限制：3秒空间限制：32768K 算法知识视频讲解 对于一个有正有负的整数数组，请找出总和最大的连续数列。
给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。
测试样例： [1,2,3,-6,1] 返回：6 分析：
状态：f(i)以array[i]结尾的连续子序列的最大和
状态递推：
f(i) = max(f(i-1) + array[i],array[i])
初始化： f(0) = array[0]
返回结果：max（f）
import numpy as np def getMaxSum_fun(A,n): if n == 0: return 0 f = np.zeros(n) f[0] = A[0] for i in range(1, n): f[i] = max(f[i-1] + A[i], A[i]) return int(max(f)) if __name__ == "__main__": print(getMaxSum_fun([6,-3,7,-15,1,22], 6))[编程题]word-break
给定字符串s和单词词典.，确定s是否可以分割为一个或多个字典单词的空分序列。 例如，给定 s =”leetcode”, dict =[“leet”, “code”]. 返回true，因为“leetcode”可以被分割为“leet code”。 分析：
import numpy as np def workbreak_fun(s, dicts): n = len(s) if len(s) == 0 or len(dicts) == 0: return False wordchack = np.zeros(n+1) wordchack[0] = True for i in range(1, len(s)+1): for j in range(0, i): if wordchack[j] and s[j:i] in dicts: wordchack[i] = True break return bool(wordchack[n]) strlist = "cars" dictlist = ["car", "ca", "rs"] print(workbreak_fun(strlist, dictlist))[编程题]triangle
给定一个三角形，从上到下求最小路径和。每一步你可以移动到下面行的相邻数字。 例如，给定以下三角形 [ 〔2〕； [3,4]， [6]，[5]，[7] [41,1,3] ] 从上到下的最小路径和是11（即2＋3＋5＋1＝11）。 注： 如果你只能使用O（n）额外的空间来做这一点，其中n是三角形中的总行数。 分析：
def minpathtotal_fun(A): if len(A) == 0 : return 0 min_sum= A for i in range(1, len(A)): for j in range(i+1): # 在最左边 if j == 0: min_sum[i][j] = min_sum[i-1][j] + A[i][j] # 最右边 elif j == i: min_sum[i][j] = min_sum[i - 1][j-1] + A[i][j] # 中间 else: min_sum[i][j] = min(min_sum[i - 1][j - 1], min_sum[i - 1][j]) + A[i][j] return min(min_sum[len(A) - 1]) num_list = [ [2], [3,4], [6,5,7], [4,1,8,3] ] print(minpathtotal_fun(num_list))
