【算法系列】——重新认识动态规划

叁歲伎倆 2022-06-09 04:40 295阅读 0赞

之前学习软考的过程，接触过动态规划的内容，但是通过最近这次的学习发现之前的理解有点偏颇，利用这次机会重新整理一下。

#     动态规划： #

是求解决策过程最优化的数学方法，把多阶段过程转换为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

#     动态规划的核心： #

1、重复子问题

2、最优子结构

保证每个过程都有最优解的最大值

动态规划运用范围极为广泛，基本上各行各业具有涉及。例如拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等，具体的应用场景见[百度百科][Link 1]

本文主要讲动态规划的思考方式，关于实现会放到下一篇博客中。

#     逆向思维，动态通用公式 #

![Center][]

![Center 1][]

如果只看第三个计算方式，有没有递归的感觉？

上述内容主要是利用动态规划解决0-1背包问题，上述公式代表在背包容量为w的前提，在i件物品中，组合出最优解的最大价值的物品组合放入背包中。

在已知最优解的前提下（也就是背包能存放的物品的最大价值已知），通过运算计算得出背包中放入了那几件物品，能得到最优解最大值。解决这个过程前提，物品和背包容量的组合都已经提前计算出来，这就是之前计算的那个表，其实表格解决的问题就是重复子问题，在拆分的过程（可以理解成递归），发现这些组合一直在重复利用，于是利用这个特点，提前计算，存储于计算机中，等需要的时候直接调用即可！

# 总结 #

理解动态规划0-1背包问题，说一万遍，也不如在感觉理解之后，先把动态规划的计算式展开，理解重复子问题的过程，然后按照思路计算一下表格的数据，理解最优子结构问题，相信在这个过程之后，对动态规划有深入的认识！下篇文章在讨论代码的实现过程！

[Link 1]: https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fr=aladdin
[Center]: /images/20220609/418400e6cbd94ba5bf18f80940f0156c.png
[Center 1]: /images/20220609/46fb49d876014b2d9df99432c0375c40.png

发表评论取消回复

表情：

评论列表（有 0 条评论，295人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-动态规划

在LeetCode上有一道题：[https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-tr

偏执的太偏执、/ 2022年12月28日 13:00/ 0 赞/ 242 阅读

相关【算法】动态规划

形成条件最优子问题重叠子问题 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a

爱被打了一巴掌/ 2022年12月01日 05:24/ 0 赞/ 196 阅读

相关动态规划算法

一：动态规划算法 1：动态规划算法介绍 1) 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获

╰半夏微凉°/ 2022年11月13日 05:28/ 0 赞/ 319 阅读

相关动态规划算法

动态规划方法是对解最优问题的一种方法，一种途径，并不是一种特殊的算法。执行步骤： 1. 找出最优解的性质，刻画结

迈不过友情╰/ 2022年08月09日 02:14/ 0 赞/ 271 阅读

相关【算法系列】——重新认识动态规划

之前学习软考的过程，接触过动态规划的内容，但是通过最近这次的学习发现之前的理解有点偏颇，利用这次机会重新整理一下。动态规划：是求解决策过程最

叁歲伎倆/ 2022年06月09日 04:40/ 0 赞/ 296 阅读

相关【算法系列】——代码实践动态规划

之前小编对算法的理解都停留在思想的层面，从未尝试过的代码实践，大家都是想出来和做出来的差距还是比较大的。小编在网上找了一个情景，所以一个实际情况的具体解析吧。问题

ゝ一纸荒年。/ 2022年06月08日 11:40/ 0 赞/ 128 阅读

相关动态规划算法

1.最长公共子串：转自：http://www.yuanma.org/data/2006/0723/article\_1215.htm 算法思想求字符串str1,st

ゝ一纸荒年。/ 2022年05月03日 15:58/ 0 赞/ 312 阅读

相关动态规划算法

1、最长公共子序列 > 定义网格：以s\[i\]和s\[j\]作为结尾的子字符串的最长子序列长度 > > 定义公式： > > s\[i\]\[j\] = s\[i

绝地灬酷狼/ 2022年03月15日 05:28/ 0 赞/ 319 阅读

相关算法——动态规划

文章目录 1.斐波那契数列 1.1递归法 1.2动态规划 1.3

怼烎@/ 2021年11月27日 02:52/ 0 赞/ 433 阅读

相关动态规划算法

一动态规划算法动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。动态规划算法与分治

╰+哭是因爲堅強的太久メ/ 2021年07月24日 22:41/ 0 赞/ 601 阅读