[动态规划] 三、最少硬币组成某面值

题目

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？
总额：11元
硬币：1元、3元、5元

动态规划问题建模阶段

设硬币面值为 value[1,3,5]，总额为 sum，硬币个数为 coin

硬币面值   |   1   3   5
——————————+—————————————
凑够 0元   |   0   0   0
凑够 1元   |   1   0   0
凑够 2元   |   2   0   0
凑够 3元   |   3   1   0
凑够 4元   |   4   2   0
凑够 5元   |   5   3   1
凑够 6元   |   6   2   2
凑够 7元   |   7   3   3
凑够 8元   |   8   2   2
凑够 9元   |   9   3   3
凑够 10元  |   10  4   2
凑够 11元  |   11  3   3

规律：
 0元 = 0
 1元 = (1-1)元硬币数 + 1 = 0+1 = 1
 2元 = (2-1)元硬币数 + 1 = 1+1 = 2
 3元 = min( (3-1)元硬币数+1, (3-3)元硬币数+1 ) = min(2+1, 0+1) = 1
 ……
11元 = min( (11-1)元硬币数+1, (11-3)元硬币数+1,（11-5)元硬币数+1 ) = min( 10+1, 2+1, 2+1) = 3

由此可见，只需要存储前面的最小硬币数，就可推出后面的最小硬币数

动态规划三个重要的概念

最优子结构：
由于有三种面值1，3，5，所以凑够11元有三种方案（选最小值）
11元硬币数 = min( (11-1)元硬币数+1, (11-3)元硬币数+1, (11-5)元硬币数+1 )
边界：
当 sum = 0, coin = 0
转态转移公式：
d(sum) = min{ d(sum-value[j])+1 } ,这里的value[j]是硬币面值[1,3,5]
(例：d(11) = min( d(11-1)+1, d(11-3)+1), d(11-5)+1 )

动态规划求解问题阶段

class Index
{
    /**
     * 动态规划（Dynamic Programming）
     * 时间复杂度：O(sum * value)
     * 空间复杂度：O(sum)
     */
    public function test()
    {
        $sum   = 11;               // 总额
        $value = array(1,3,5);     // 硬币面值
        $coin  = array();          // 最少硬币数量
        $v_len = count($value);    // 每迭代一层都需要循环3次硬币面值

        // 给存放最少硬币数量的数组赋初始值，不能全初始化为 0，否则在下个 for 内层循环的 if 出错
        for ($i = 0; $i<=$sum;$i++) {
            $coin[$i] = $i;
        }

        // 循环总额，即迭代表格每一层
        for ($i = 0; $i <= $sum; $i++) {
            // 循环硬币面值 1 3 5
            for ($j = 0; $j < $v_len; $j++) {
                // 如果当前金额>=硬币面值 && 最少硬币[当前金额-当前硬币面值]+1<最少硬币[当前金额]
                if ($i >= $value[$j] && $coin[$i-$value[$j]]+1 < $coin[$i]) {
                    // d(sum) = min{ d(sum-value[j])+1 }
                    $coin[$i] = $coin[$i-$value[$j]]+1;
                }
            }
        }
        halt($coin);
    }
}

参考：动态规划