专栏首页木子昭的博客白话版 动态规划法

白话版 动态规划法

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷leetcode的时候,发现了一个很不错的关于动态规划算法的例题,特来分享一下!

Leetcode120

这是一个典型的动态规划问题:

  • 在走第N步的之前, 第1步到第N-1步已经达到了最优.
  • 走出第N步之后, 第N-1步的最优就要动态变化为"相对最优",而第一步到第N步依然是最优.

动态规划法的优势在于, 前面N-1步保持了"很多"状态, 当走出第N-1步的时候后, 可以基于保存的状态直接得出"很多新的"状态, 然后从新状态中得到最优解.

为了简化问题, 对于上面的题目,我们可以从底向上走:

动态规划法

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        for m in range(len(triangle)-1)[::-1]:
            # m 为 主数组索引
            if (m == len(triangle)-1):
                pass
            # n 为当前元素索引
            for n in range(len(triangle[m])):
                triangle[m][n] = min(triangle[m][n]+triangle[m+1][n], triangle[m][n]+triangle[m+1][n+1])
                print("第",m,"行", "第",n,"个元素当前值为", triangle[m][n])      
                
        return triangle[0][0]
                
            
def main():

    result = Solution().minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]])     
    print("最短路径为==>",result)
            
        
if __name__ == '__main__':
    main()

动态规划法结果

动态规划与贪心法的区别:

  • 贪心只考虑当前最优, 只保留当前最优的状态;
  • 动态规划法, 不仅保留了当前最优,而且保留了(很多)相对最优的状态

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用Electron创建跨平台应用(第一弹)

    zhaoolee
  • 《哔哩哔哩助手》助你快速成为B站老司机

    B站全名哔哩哔哩,域名bilibili.com ,名字源于《魔法禁书目录》中 御坂美琴 的昵称,所以B站动漫出现 bilibili译制的字样时, 会有很多弹幕刷...

    zhaoolee
  • 新媒体必修课: 如何快速将gif图调整到300帧以内?

    ​为保证最终gif图的流畅,可以采用每隔N帧,抽取1帧的方式, 一张504帧的图片,我们需要每隔1帧抽取1帧微信一直以「克制」著称,为了给用户节省流量,微信公众...

    zhaoolee
  • 手撕Netty-用Java NIO完成Netty Reactor思想,助你理解Netty模型事件驱动

    这是Netty官网上的一段介绍。我们主要关注它的可维护,高性能,高可伸缩性,使用Netty可以简化网络编程,并且性能优秀!

    行百里er
  • 从零开始搭建个人博客(spring boot)-实现列表,详情,分页功能

    ①settings->Build,Execution,Deployment->compiler,勾上

    AI码师
  • Linux 下 Bugzilla 的安装及配置

    Bugzilla 是一个基于 Web 的,开源的,用来记录跟踪缺陷数据库的 bug 跟踪软件。它可以管理软件开发中缺陷的提交(new)、修复(resolve)和...

    悠风
  • 火绒产品公告——企业版推出“终端动态认证”功能 阻止RDP弱口令渗透

    火绒针对企业用户终端的防护新增“动态认证”功能,开启后,通过登录终端时(包括远程和本地登录)进行二次验证的方式,阻止终端遭遇密码泄露、弱口令暴破、撞库等黑客破解...

    用户6477171
  • 家装、餐饮、电商、地产信息流广告投放策略和案例

    最近比较多的时间在研究流量,其实单单就“流量”两个字包含的就非常多,在研究的过程中也搜集了很多案例,并且尝试与数据结合起来,具体资料如下:

    沉默的白面书生
  • Django权限机制的实现

    权限机制能够约束用户行为,控制页面的显示内容,也能使API更加安全和灵活;用好权限机制,能让系统更加强大和健壮。因此,基于Django的开发,理清Django权...

    菲宇
  • 同样做前端,为何差距越来越大?

    过去一年,阿里巴巴新零售事业群支撑的数据相关业务突飞猛进,其中两个核心平台级产品代码量急速增长,协同开发人员增加到数十人。

    IT大咖说

扫码关注云+社区

领取腾讯云代金券