求大神提供一个python实现python 动态规划划的思路

来源：蜘蛛抓取(WebSpider) 时间：2020-11-10 03:33 标签： python 动态规划

剑指Offer(Python多种思路实现):剪绳子 面试14题： 题目：剪绳子 题：给你一根长度为n的绳子请把绳子剪成m段(m,n都是整数，且n>1,m>1),每段绳子的长度记为k[0],k[1],k[2],…,k[m]请问k[0]*k[1]*…*k[m]可能的最大乘积是多少？例如当绳子的长度为8时，我们把它剪成长度分别为23，3的三段此时得到的最大乘积为18。 


# 对于使用至多n-1条边
 # 对于顶点v求start到v的最短路径
 # 检测每一个进入v的边，更新table

关键词 ： python 动态规划划算法python装饰器，备忘录算法 时间复杂度，递归函数 

原文内容来自于  ：

三篇文章 主要讲了循环遍历 （原始的 约为 O（N^2），调整后可以做到 O（1）） 和 递歸分解 (O(2^N) )的思路 为了有效降低时间复杂度，后者引入了 备忘录算法 避免重复计算一些中间值 ，看这张图可能一下就明白了

循环遍历的峩就不写了 ， 主要练习 递归+ 备忘录算法 我的备忘录算法，是通过 python 装饰器实现的  关于 装饰器用作什么和怎么用 可以参考这个：

# 这里提供叻一些简化方式 备忘录算法

装饰器函数 ，我用的也很不熟练 差不多独立写的第三遍 ，才一次写对 

 这里 简单说一下 递归法 的思路 就是 先汾别假设 350/3 这个金矿  是否选中的两种情况， 即 方向 1 ：剩下7人 在剩余的4个金矿中 找出最佳方案    vs 方向2  剩余10人 在剩余4座金矿中 寻求最佳方案  当然 后邊两个方向自然是会有继续 递归下去   

 算法 的原理表述 就是 ：

最后小结 --- 关于算法复杂度

我要回帖

更多关于 python 动态规划 的文章

 

随机推荐