【C语言学习笔记】算法篇——动态规划_c语言动态规划

浅谈动态规划Dynamic Programming

写在前面：

学习这个算法的缘由其实是这篇博客，当时在写完这道题的题解时，师兄好心地提醒我有一个说法不太准确，就是到底是不是贪心算法，在学习了动态规划后发现这两者真的有挺多共同点的。且上次月赛挺多题目都涉及到了动态规划的思想，故今天来整理一下，先立个FLAG，这篇博客应该要写很久很久很久…

---

什么是动态规划？

首先要了解的是，和贪心算法一样，动态规划算法只是一种思想，不是像排序算法一样有具体的代码。

我第一次学习动态规划，是在《算法图解》这本书中，因此后面的一些内容会摘自原书，若有侵权，请联系删除。作者通过背包问题、旅游行程最优解、最长公共子串、最长公共子序列四个典型的案例来讲解动态规划，四个案例无一都是通过表格法找出答案的

一些重要笔记

沿着一列往下走时，最大价值不可能降低，因为每次迭代时，你都存储当前的最大价值。最大价值不可
能比以前低！

要以最小单位划分表格

要逐行填充不要逐列填充

使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。但使用贪婪算法可轻松地处理这种情况！

。动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用 。

根据动态规划算法的设计，最多只需合并两个子背包，即根本不会涉及两个以上的子背包。不过这些子背包可能又包含子背包。

最优解的情况可能没利用完空间/时间

9.4　小结
需要在给定约束条件下优化某种指标时，动态规划很有用。
问题可分解为离散子问题时，可使用动态规划来解决。
每种动态规划解决方案都涉及网格。
单元格中的值通常就是你要优化的值。
每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
没有放之四海皆准的计算动态规划解决方案的公式。

我觉得书上面的一些理解已经非常详细且准确了，这里就不再重复叙述了。这里我想再重复一点的就是这句话每种动态规划解决方案都涉及网格。这句话已经非常的绝对了，而往往在题目中的表现就是用二维数组来创建“表格”，在根据题目背景写入值的同时计算出结果。

2020/11/6修正一下，不是所有的DP都是二维的，有一维的也有三维四维高维的DP，但大部分常见的都是二维的，或者说高维可以优化降到二维，或者一维可以用二维轻松解决。

---

如何设计动态规划？

依旧引用《算法图解》的文字

要设计出动态规划解决方案可能很难，这正是本节要介绍的。下面是一些通用的小贴士。
1.每种动态规划解决方案都涉及网格。
2.单元格中的值通常就是你要优化的值。在前面的背包问题中，单元格的值为商品的价值。
3.每个单元格都是一个子问题，因此你应考虑如何将问题分成子问题，这有助于你找出网格的坐标轴。

其实，根据上述的内容，好像对做题还是没有很明确的指示，那么再往下读，你就看到

用于解决这个问题的网格是什么样的呢？要确定这一点，你得回答如下问题。
1.单元格中的值是什么？
2.如何将这个问题划分为子问题？
3.网格的坐标轴是什么？

！！！这三个条件是可执行的，不想上方的小贴士，那更像是大量统计的统计结果而已，而这三条才是正在解决问题的方向，当自己很疑惑，不知道要如何去设计这道题的动态规划时，不妨试试先从解决这三个问题开始，值是什么？如何划分为子问题？坐标轴是什么？其实当你解决了这三个问题，题目也就迎刃而解了。

实际上，根本没有找出计算公式的简单办法，你必须通过尝试才能找出管用的公式。有些算法并非精确的解决步骤，而只是帮助你理清思路的框架。

书上当时还幽默地提到了费曼算法，不要想着绝对通用的方法。

---

与其他算法千丝万缕的关系

DP与DFS：

之前我的博客有浅谈过DFS，其实DFS我也只是略懂一二，不能给出很深刻的见解，但我这里强烈推荐一个博主的分析，语言通俗易懂，结合案例讲解，也讲述了DP中几个重要的概念，非常适合新手阅读。

ACM0基础动态规划启蒙：Dp是个啥

DP与贪心：

DP与贪心最大的区别，可能就是结果了，贪心是利用局部最优解来求整体最优解，但往往有些情况下，局部最优的和并不是整体最优，因为你忽略了全局观，贪心的每一步都只关系这一步的最优，而没有放眼全局顶层设计，这也是导致结果不一定是最优的原因。其实贪心二字就给人感觉鼠目寸光的感觉，没有大局观。