动态规划
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决
基本思路
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
算法实现
使用动态规划求解问题，最重要的就是确定动态规划三要素：
（1）问题的阶段-----问题的边界
（2）每个阶段的状态-----最优子结构
（3）从前一个阶段转化到后一个阶段之间的递推关系------转态转移公式
实例分析
实例1 爬楼梯
- 问题描述
有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法
- 问题分析
状态方程：F(1)=1,F(2)=2,F(n)=F(n-1)+F(n-2)(n>3)
- 代码实现
class Solution: def climbStairs(self, n): """ :type n: int :rtype: int """ # 递归 time limit # if n==1 or n==2: # return n # return Solution.climbStairs(self,n-1)+Solution.climbStairs(self,n-2) ## 备忘录算法 time limit # data={} # if n==1 or n==2: # return n # if n in data: # return data['n'] # else: # value=Solution.climbStairs(self,n-1)+Solution.climbStairs(self,n-2) # data['n']=value # return value ## 动态规划 if n==1 or n==2: return n first=1 second=2 temp=0 for i in range(n-2): temp=first+second first=second second=temp return temp
