动态规划入门动态规划入门
需积分: 21 131 浏览量
2023-01-06
18:47:21
上传
评论
收藏 1006KB DOCX 举报
C++ 不知算法系列之深入动态规划算法思想
1. 前言
前面写过一篇博文，介绍了什么是动态规划算法。动态规划算法的最大特点，
原始问题可以通过分解成规模更小的子问题来解决，子问题之间互成依赖关
系，也就是先计算出来的子问题的结果会影响到后续子问题的结果。
有点类似于武侠片中，主角受伤后，一群江湖侠士排成一队，最后一人把真气
传递给前面的、前面的再传递给他前面……如此传递，最后传递了主角，主角
获得了所有人的真气。
真气传递过程中，每一个人就是一个子问题，如果每一个人传递出去的真气是
个体最大的，则最后主角获取到的真气必然也是最大的。也是动态规划中的最
优子结构的概念。
本文通过几个案例，深入探讨动态规划。
2. 案例
2.1 最短路径
2.1.1 问题描述
求解如下有向权重图中从 A 城市到 E 城市之间的最短路程。城市与城市之间的
连接线上的数字表示城市之间的路程。
剩余12页未读，继续阅读
资源评论
