最近在看关于数据结构系列知识点，然后遇到一个动态规划相关的题目——邮票规划。
首先先介绍下关于DPS，也就是深度优先遍历算法吧。
深度优先遍历
深度优先遍历，从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
一句话的事情：优先进行纵向访问，而不是广度优先遍历的横向进行访问
动态规划相关知识点
动态规划算法的基本思想是：将带求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解中得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，避免重复求解。该思想与记忆化搜索类似，即将计算步骤中的过程保存下来，避免重复运算
要点：
- 动态规划适用于这些子问题不是独立的情况，也就是各子问题包含公共子问题
- 需要记录每个子问题求解的问题结果，以供其他问题进行解决
相关步骤
- 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
- 确定状态和状态变量：注意状态必须满足无后效性。
- 确定决策：找到子问题是进行动态规划的重要一步。动态规划和递推更多应考虑本问题由哪些已解决子问题构成，而不是考虑本问题对将来哪些问题有贡献。
- 确定边界条件，写出状态转移方程
具体事例
问题描述
给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤13）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。
例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
输入格式
一行，两个数N、K
输出格式
两行，第一行升序输出设计的邮票面值，第二行输出“MAX=xx”（不含引号），其中xx为所求的能得到的连续邮资最大值。
样例输入
3 2
样例输出
1 3
MAX=7
当看到这个问题我们藉由之前的理论来具体分析下。
动态规划
- 子问题
- 是否选择面值各大的邮票呢，这里显示选择只能“是”或者“否”
- 最优子结构
- 当然同理，连续邮票的面值在每个值下都成立，这样就构成了结构。
- 边界
邮票的种类数目
当然有了上面的几点，我们试着写下该方式的转化方程，假如n代表邮票总共类别，i代表邮票总面值，stamp[i]代表邮票所属值大小，dp[i]代表凑齐 i 面值最少需要多少邮票，Dp(int position)代表几种类别的所能组成邮票值。
- 当i >= stamp[k] && dp[i] > dp[i - stamp[k]] + 1，则 dp[i] = dp[i - stamp[k]] + 1;就是说取最大的那个。
- 当dp[i]>n，Dp(position)=i,
- 当dp[i]<n,Dp(postion)=-1;就是说无意义
DPS的使用
- deep深度——由于每个邮件的类别数目难以确定，所以需要以邮票数目为DPS的递归深度deep）
- 中止条件——当确定最大连续能取得值maxm，那么新加入的物品价值一旦大于maxm+1，显然就会出现断层，所以可以以maxm+1为枚举上界，然后这样进行下一层的dfs。
附上java代码：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N=500;
static int n,m,ans;
static int a[]=new int[N+1];
static int b[]=new int[N+1];
static int f[]=new int[N+1];
public static void main(String[] args) {
int i,j,k;
Scanner scanner =new Scanner(System.in);
n=scanner.nextInt();
m=scanner.nextInt();
a[1]=1;
dfs(1);
for(i=1;i<=m;i++)
System.out.printf("%d ",b[i]);
System.out.printf("\nMAX=%d\n",ans);
}
static void dfs(int deep)
{
int i,j,uplimit;
Arrays.fill(f,0x3f);
f[0]=0;
for(uplimit=1;uplimit<=N;uplimit++)
{
for(i=1;i<=deep&&a[i]<=uplimit;i++)
f[uplimit]=Math.min(f[uplimit],f[uplimit-a[i]]+1);
if(f[uplimit]>n)
{
uplimit--;
if(uplimit>ans)
{
ans=uplimit;
for(i=1;i<=deep;i++)
b[i]=a[i];
}
break;
}
}
if(deep==m)return ;
for(i=uplimit+1;i>a[deep];i--)
{
a[deep+1]=i;
dfs(deep+1);
}
}
}
