白话版 动态规划法

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷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 条评论
登录 后参与评论

相关文章

来自专栏数值分析与有限元编程

Newton–Raphson法解串联弹簧问题

如图所示的串联弹簧,F=100,弹簧刚度为k1 = 50 + 500u ,k2 = 100+ 200u ,u是弹簧伸长量,则平衡方程为 ? ? k1,k2带入得...

2866
来自专栏大数据

大数据计数原理1+0=1这你都不会算No.77

完结篇。 这个系列写到这里算是结束了,真是不容易说实话,查了好多好多的资料,真的很难相信懒得要命的我能写完这个系列 T_T。有兴趣的小伙伴可以在菜单看看整个系列...

2195
来自专栏数据科学与人工智能

【Python环境】R vs Python:硬碰硬的数据分析

我们将在已有的数十篇从主观角度对比Python和R的文章中加入自己的观点,但是这篇文章旨在更客观地看待这两门语言。我们会平行使用Python和R分析一个数据集,...

3059
来自专栏WOLFRAM

Mathematica 11在代数与数论中的新功能

1855
来自专栏杨熹的专栏

使聊天机器人具有个性

本文结构: 模型效果 模型的三个模块 模块细节 ---- 今天的论文是 《Assigning Personality/Identity to a Chattin...

3548
来自专栏游戏开发那些事

【小白学游戏常用算法】二、A*启发式搜索算法

  在上一篇博客中,我们一起学习了随机迷宫算法,在本篇博客中,我们将一起了解一下寻路算法中常用的A*算法。

1662
来自专栏鸿的学习笔记

写给开发者的机器学习指南(七)

Classifying email as spam or ham (NaiveBayes)

1241
来自专栏机器人网

机器人A*寻路算法详解

A*(A-star)算法是一种静态网路中求解最短路径最有效的直接搜索算法。在电子游戏中最主要的应用是寻找地图上两点间的最佳路线。在机器人领域中,A*算法...

3704
来自专栏Coding迪斯尼

神经网络实战:快速构建一个基于神经网络的手写数字识别系统

1262
来自专栏落影的专栏

OpenGL ES不容错过的实战-碰碰车

教程 OpenGLES入门教程1-Tutorial01-GLKit OpenGLES入门教程2-Tutorial02-shader入门 OpenGLES入门...

2905

扫码关注云+社区

领取腾讯云代金券