Question

用动态规划求出了最优的状态后,怎么得到具体的方案呢?

如题，这是一个简单的动态规划求硬币的问题，
有1，3，5面值的硬币若干个(个数不限),求最小的硬币个数筹齐11元。这个我求得的最优的状态是3。用眼睛可以看出选择的是(5,5,1).但是怎么推出这个结果？

Answer 1

回溯
你会知道11元最小是3枚，11-1 元最小是2枚，所以11元可以含有1个1元
然后10-1元需要最少3枚，所以不可能再包含1元
10-3元需要最少3枚，所以也不可能包含3元
10-5元需要至少1枚，所以10元里面可以含有1个5元
5-5元需要0枚，所以5元可以含有1个5元

综上，我们回溯可得，11元可有1个1元，2个5元组成最少的3枚硬币

追问

这个完全脱离之前得到的状态吗？就是动态规划得到的状态

追答

不脱离啊，动态规划过程，不是已经算好了每个面值最少需要多少枚了吗？
如果dp[M] = k, dp[N] = k-1, N < M, 存在面值为M-N的硬币
那么说明组成M面值的最少的k个硬币里面，有一个是M-N的硬币，剩下的k-1枚组成N面值
一直重复直到M变成0

追问

哦哦，非常感谢你的回答