白话版 动态规划法

简介: 关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷leetcode的时候,发现了一个很不错的关于动态规划算法的例题,特来分享一下!Leetcode120这是一个典型的动态规划问题:在走第N步的之前, 第1步到第N-1步已经达到了最优.

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷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()
动态规划法结果

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

  • 贪心只考虑当前最优, 只保留当前最优的状态;
  • 动态规划法, 不仅保留了当前最优,而且保留了(很多)相对最优的状态
目录
相关文章
|
2月前
|
算法
第七章 回溯算法理论基础
第七章 回溯算法理论基础
22 0
|
7月前
【编程题-错题集】非对称之美(找规律 / 贪心)
【编程题-错题集】非对称之美(找规律 / 贪心)
|
7月前
|
算法
贪心算法个人见解
贪心算法个人见解
|
算法 算法框架/工具
图论算法实例分析|趣味象棋
图论(graph theory)是数学的一个分支,以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。
130 0
图论算法实例分析|趣味象棋
|
搜索推荐 算法
离散数学_九章:关系 —— 拓扑排序
离散数学_九章:关系 —— 拓扑排序
162 0
|
Java
【回溯法】求解多种组合问题【java实现】
【回溯法】求解多种组合问题【java实现】
67 0
|
算法 测试技术
动态规划真的有那么抽象吗?(递推算法还是动态规划别傻傻分不清了) 以正确的姿势学习动态规划 (入门篇)
动态规划真的有那么抽象吗?(递推算法还是动态规划别傻傻分不清了) 以正确的姿势学习动态规划 (入门篇)
动态规划真的有那么抽象吗?(递推算法还是动态规划别傻傻分不清了) 以正确的姿势学习动态规划 (入门篇)
|
算法
【算法设计与分析】动态规划法与分治法、贪心法的区别
【算法设计与分析】动态规划法与分治法、贪心法的区别
324 0
|
人工智能 移动开发 算法
再学一道算法题: 种树(贪心)
再学一道算法题: 种树(贪心)