10 | 动态规划（下）：如何求得状态转移方程并进行编程实现？

[yujiangshui]

[yujiangshui]

补充一下在这个钱币公式中 arg 的意思：

arg    是变元（即自变量argument）的英文缩写。 arg min 就是使后面这个式子达到最小值时的变量的取值 arg max 就是使后面这个式子达到最大值时的变量的取值

例如 函数F(x,y): arg  min F(x,y)就是指当F(x,y)取得最小值时，变量x,y的取值 arg  max F(x,y)就是指当F(x,y)取得最大值时，变量x,y的取值 ———————————————— 版权声明：本文为CSDN博主「JayMining」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/JayMining/article/details/52723759

[yujiangshui]

所以表达的意思就是 j 从 1 到 n 循环，求后面公式的运算结果的最小值。

我的推导过程如下，以总额为 11 钱币为 [1, 2,5] 为例，假设 C(11) 表示最终的结果，那么就可以得出：

C(11) = C(10) + 1; // 假设先找一张 1 块钱
C(10) = C(9) + 1; // 再来一张 1 块钱
...
C(0) = 0;
C(11) = C(10) + 1 = C(9) + 1 + 1 ... = C(0) + 11 = 11 张，都用一块的需要 11 张

假设先找五块的，同理：

C(11) = C(6) + 1; // 五块
C(6) = C(1) + 1; // 五块
C(1) = C(0) + 1; // 一块

那么这种方案就是三张完成。

由于条件需要最少解决方案，那么就是第二种方案。所以得到的公式类似于：

C(n) = C(n - 某一张纸币的金额) + 1

在实际运算的时候，就可以先从最小额开始算起，并且逐步积累最小数量的结果，当算到大额的时候，拆分成小额后，可以直接读取计算对应计算结果 + 1 即可。