python动态规划算法实例详解

如果大家对这个生僻的术语不理解的话，那就先听小编给大家说个现实生活中的实际案例吧，虽然现在手机是相当的便捷，还可以付款，但是最初的时候，我们经常会使用硬币，其中，我们如果遇到手中有很多五毛或者1块钱硬币，要怎么凑出来5元钱呢？这么一个过程也可以称之为动态规划算法，下面就来看下详细内容吧。

从斐波那契数列看动态规划

斐波那契数列：Fn = Fn-1 + Fn-2 （ n = 1,2 fib(1) = fib(2) = 1）

练习：使用递归和非递归的方法来求解斐波那契数列的第 n 项

代码如下：

# _*_coding:utf-8_*_
def fibnacci(n):
  if n == 1 or n == 2:
    return 1
  else:
    return fibnacci(n - 1) + fibnacci(n - 2)
 print(fibnacci(10)) # 55

如果看不懂上面模棱两可的介绍，还有下面直观的代码：

f(1) = 1
f(2) = 1
f(3) = f(1) + f(2) = 1+ 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
...
f(n) = f(n-1) + f(n-2)

实例扩展：

爬楼梯

假设你正在爬楼梯，需要n阶才能到达楼顶
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
如：
示例1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解析：

如果给的两个示例看的不是特别清楚，你可以当阶梯为0，那么上楼梯方法0种这是必然，当阶梯只有1那么上楼梯方法只有1种：
当4个台阶：
输入：4
输出：4
1. 1阶 + 1阶 + 1阶 + 1阶
2. 2阶 + 2阶
3. 1阶 + 2阶 + 1阶
4. 2阶 + 1阶 + 1阶
5. 1阶 + 1阶 + 2阶
那么得到：
阶梯数 爬楼梯方法
0 0
1 1
2 2
3 3
4 5
...
如果感觉看的不明显可以推理一下5阶，6阶...
可以得到当我们想爬n阶楼梯，我们可以得到： p(n-1) + p(n-2) p为爬楼梯方法

class Solution:
  def climbStairs(self, n: int) -> int:
    num_list = [0,1,2]
    if n==1:
      return num_list[1]
    elif n==2:
      return num_list[2]
    else:
      for i in range(3,n+1):
        num_list.append(num_list[i-1]+num_list[i-2])
    print(num_list)
    return num_list[n]

obj = Solution()
result = obj.climbStairs(10)
print(result)

提交LeetCode只击败了12.72%的人。通过优化

class Solution:
  def climbStairs(self, n: int) -> int:
    a,b,c = 0,1,2
    if n == 1:
      return b
    if n == 2:
      return c
    while n>0:
      c = a + b
      a,b = b,c
      n -= 1
    return c
obj = Solution()
result = obj.climbStairs(8)

到此这篇关于python动态规划算法实例详解的文章就介绍到这了,更多相关python动态规划算法是什么内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Python基于动态规划算法解决01背包问题实例

    Python基于动态规划算法解决01背包问题实例

    本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re

  • python实现对求解最长回文子串的动态规划算法

    基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解 对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含

  • Python基于动态规划算法计算单词距离

    本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("

  • python动态规划算法实例详解

    如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱硬币,要怎么凑出来5元钱呢?这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧. 从斐波那契数列看动态规划 斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的第 n 项 代码如下: #

  • KnockoutJS数组比较算法实例详解

    这篇文章主要介绍了KnockoutJS数组比较算法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 前端开发中,数组是一种非常有用的数据结构.这篇博客会解释并分析KnockoutJS实现中使用的数据比较算法. 算法的目的 KnockoutJS使用MVVM的思想,view model中的数组元素会对应data model中的数组数据,当用户进行输入或者请求后台时,数组数据会发生变更, 从而带动UI的更新.例如购物车类的页面,用户可以通过点击

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

  • Python 调用Java实例详解

    Python 调用Java实例详解 前言: Python 对服务器端编程不如Java 所以这方面可能要调用Java代码 前提: Linux 环境  1 安装 jpype1 安装后测试代码: from jpype import * startJVM(getDefaultJVMPath(), "-ea") java.lang.System.out.println("Hello World") shutdownJVM() 2 调用非jdk的jar包, test.jar 包

  • python 系统调用的实例详解

    python 系统调用的实例详解               本文将通过两种方法对python 系统调用进行讲解,包括python使用CreateProcess函数运行其他程序和ctypes模块的实例, 一 python使用CreateProcess函数运行其他程序 >>> import win32process >>> handle = win32process.CreateProcess('c:\\windows\\notepad.exe','',None,None

  • Python 加密的实例详解

     Python 加密的实例详解 hashlib支持md5,sha1,sha256,sha384,sha512,用法和md5一样 import hashlib #hashlib支持md5,sha1,sha256,sha384,sha512,用法和md5一样 m = hashlib.md5() #创建加密对象 m.update(b'password') #对输入内容进行加密, m.digest() #获取二进制加密密文 m.hexdigest() #获取十六进制加密密文 '''''python3默认

  • Python 异常处理的实例详解

    Python 异常处理的实例详解 与许多面向对象语言一样,Python 具有异常处理,通过使用 try...except 块来实现. Note: Python v s. Java 的异常处理 Python 使用 try...except 来处理异常,使用 raise 来引发异常.Java 和 C++ 使用 try...catch 来处理异常,使用 throw 来引发异常. 异常在 Python 中无处不在:实际上在标准 Python 库中的每个模块都使用了它们,并且 Python 自已会在许多不

  • Python字符串处理实例详解

    Python字符串处理实例详解 一.拆分含有多种分隔符的字符串 1.如何拆分含有多种分隔符的字符串 问题: 我们要把某个字符串依据分隔符号拆分不同的字段,该字符串包含多种不同的分隔符,例如: s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz" 其中;,|,\t 都是分隔符号,如何处理? 方法一: 连续使用str.split()方法,每次处理一种分隔符号 s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz&q

  • JavaScript算法系列之快速排序（Quicksort）算法实例详解

    JavaScript算法系列之快速排序（Quicksort）算法实例详解

    "快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边. (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止. 举例来说,现在有一个数据集{85, 24, 63, 45,

  • Python 多线程的实例详解

     Python 多线程的实例详解 一)线程基础 1.创建线程: thread模块提供了start_new_thread函数,用以创建线程.start_new_thread函数成功创建后还可以对其进行操作. 其函数原型: start_new_thread(function,atgs[,kwargs]) 其参数含义如下: function: 在线程中执行的函数名     args:元组形式的参数列表.     kwargs: 可选参数,以字典的形式指定参数 方法一:通过使用thread模块中的函数创

随机推荐