动态规划 | SZU

最近刷 leetcode 遇到了一道题目，没有什么头绪，看了答案说是需要用到动态规划，
刚好对动态规划也没有学习过，就去查阅了一些相关的文章，这里记录一下心得和体会。
分享一下我看的这篇文章，感觉整体上讲的还是挺不错的，由浅入深(http://www.hawstein.com/posts/dp-novice-to-advanced.html)[http://www.hawstein.com/posts/dp-novice-to-advanced.html]。

这里我还是用三段式来学习一个新的知识。

是什么

动态规划是一种思想，并没有一种具体的实现方式，它在我们求解一些问题的时候可以给我们提供一个思路。动态规划需要我们学会如何拆分问题。
通常这些问题会具有以下特征：每一个阶段的决策会影响到后面的决策，

为什么要用动态规划结果就很显而易见了，因为我们需要一种较为高效的方式来寻找到最优解。

要用好这一种思想，最重要的就是要学会如何拆分问题，当我们把问题拆分出来了，整个解决思路就自然而然的寻找到了。

动态规划最终要做的就是找到状态定义和状态转移方程。

这里拿一个简答的动态规划的题目做例子。有三种硬币，1，3，5 元，最少需要多少硬币能够达到总数n元

计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态。

我们可以设n元需要的最少硬币数为d(n),这就可以看做是一个状态, 显然 d(0) = 0, d(1) = 1,

d(2) 可以被转化成 d(1) + 1 = 2

d(3) 可以被转化成 d(3 - 1) + 1 = d(2) + 1 = 3 和 d(3 - 3) + 1 = d(0) + 1 = 1, 显然后者更小

d(4) 可以使被转化成 d(4 - 1) + 1 = d(3) + 1 = 2 和 d(4 - 3) + 1 = d(1) + 1 = 2, 两者一样大

d(5) 可以被转化成 d(5 - 5) + 1 = d(0) + 1 = 1、d(5 - 3) + 1 = d(2) + 1 = 3、d(5 - 1) + 1 = d(5) + 1 = 3,显然1最小

我们可以把 d(n) 看做是 d(n) = min(d(n - Vi) + 1); n - Vi >= 0; Vi = [1, 3, 5];

总的来说，动态规划需要我们找到问题的子问题，再从子问题找到状态转移方程，最后找到解决的方法