动态规划算法总结

2022-05-17 136

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 动态规划算法总结

动态规划

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决

基本思路

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

算法实现

使用动态规划求解问题，最重要的就是确定动态规划三要素：

（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