|
本文参考刘汝佳《算法竞赛入门经典》（第2版）* 动态规划的核心是状态和状态转移方程**
DAG上的动态规划一定要结合图来思考，要心中有图，或者在纸上画图，谨记！这样可以真正理解！求解状态转移方程的过程其实就是在填写一个表格！把表填好了，所有状态就填好了
硬币问题
 【说明】 DAG上的动态规划问题！笔者“建立的图”都是从S到0。d(i)定义为以i开始到0结束的最长/短路。具体看下面代码及相关注释。 ##记忆化搜索求解
/*
【本代码求解最少硬币】
状态确定：必须是从S状态到0状态（注意这里状态的含义），这些状态其实就是DAG上的点，每种面值就是边。
***注意下面代码建的图是从S到0建图的（从0到S建图也可以）。并且d(i)定义为从状态i到状态0的最短路,
当然也可以定义d(i)为从状态S到状态i的最短路（即以状态i结束的最短路）
S -> 0
1）求最多硬币（类似于最少硬币情况，只需改动本代码的三处，注释中已经标明）
d(i)表示从状态i到状态0的最长路
d(i)=max{d(j)+1 | (i,i-coin[j])∈E} ,(i,i-coin[j])∈E的意思就是i>=coin[j]
边界情况：d(0)=0
预处理：d(i)=-1，表示还没有访问过
初始化：d(i)=-INF，为了无解情况标记
无解：d(i)的最终结果是负数
2）求最少硬币（本代码解决该问题）
d(i)表示从状态i到状态0的最短路
d(i)=min{d(j)+1 | (i,i-coin[j])∈E},(i,i-coin[j])∈E的意思就是i>=coin[j]
边界情况：d(0)=0
预处理：d(i)=-1，表示还没有访问过
初始化：d(i)=INF，为了无解情况标记
无解：d(i)的最终结果是INF
*/
/*
求解动态规划的状态转移方程，可以使用递归+记忆化搜索，或者使用递推（填表法）。下面使用
这两种方法求解最小硬币数。（最大硬币数很类似，只需稍作改动，后面直接给出相应代码。）
*/
#include
#include
using namespace std;
const int maxn=1005;//假设硬币面值最大种类数
const int INF = (1 |