题目
思路
1. 第二题在编程之美上以例题的形式给出, 书上给出的解法是剪枝. 这边是把只含01的数变成 1 + 10 + 100... 的问题
dp[i][j] 表示前 i 个数组成的mod n 余数为 j 的最小值
dp[i][j] = min(dp[i-1][j], dp[i-1][r]+10^i)
2. 第四五题类似. 找零问题. dp[i] 表示支付 i 钱需要的最少货币数. dp[v] = min(dp[v-w[i]], dp[v+w[i]]) + 1
注意, 因为需要找钱, 所以 v 设置的大一些
3. 第六题. 背包变形. 先枚举第 k 件物品是没被放下的重量最小的物品, 那么小于 k 的全部被放下了, 对剩下的背包进行 01 背包即可