动态规划（Dynamic Programming）

一、简介

        我们先举个例子让大家明白动态规划到底是什么？

        1+1+1+1+1的结果是5，那如果我们在上面等式的前面再加上一个“1+”，那结果是什么呢？很多人都会立刻回答：“是6。”那为什么回答地怎么快呢？是因为我们已经知道1+1+1+1+1是5这就是动态规划。

        动态规划的基本思想与分治法类似，也是将一个大问题分解成若干个子问题，前一个子问题的解为后一个子问题的解提供了有效的信息。在求解子问题是，列出各种可能的局部解，通过决策保留那些可能达到最优的局部解，丢弃其他局部解。一次解决各个子问题，最后一个子问题的解就是大问题的解。

        由于动态规划解决的问题大部分都有重叠子问题这个特点，为了减少重复计算，对每个子问题之求解一次，将其不同阶段的不同状态保存在二维dp数组中。

        动态规划与分治的区别：适用于动态规划求解的问题，经分解后得到的子问题往往不是相互独立的（即下一个子阶段的解是建立在上一个子阶段的解的基础上的）。

二、步骤

1. 将大问题化成子问题：对于动态规划，重要的是如何把一个大问题化为若干个小问题。可以通过逐级降阶的方法将问题简单化，从而实现问题的求解。
2. 找出状态转移方程，把问题方程化。
3. 按照实际逻辑设置边界条件和初始条件。
4. 确定顺序并求解。

三、题目分析 

原题

        目前有9元、5元和2元三种硬币无限枚，现在要找回21元硬币，则用怎么样的组合可以使得使用的硬币最少？

分析

        利用动态规划解决该题目。分以下四个步骤：

（1）大问题化成子问题

        假设拿出的硬币分别是a1、a2、a3、…、ak，一空有k枚硬币。从最后一步分析：把所有硬币减去最后一枚ak，得到了一个k-1枚硬币的子问题；由于本题要利用最少的组合兑换，所有k-1枚子问题也是最小组合。

（2）状态转移方程

        设状态dp[i]=最少用多少枚硬币拼凑出i；

        则状态转移方程：dp[i]=min(dp[i-9]+1,dp[i-5]+1,dp[i-2]+1);

        该方程的意思是：要想求出i的最少组合方法，则应当求出i-9、i-5和i-2中的最小值，加上1就是现在的解。

（3）初始条件与边界值

        考虑初始条件，dp[0]=0，表示0元需要0个硬币。

        边界条件为：当x-2、x-5和x-9小于0时结束。

（4）计算顺序

        根据初始条件dp[0]，依次计算dp[1]dp[2]dp[3]…dp[21]，具体过程如下。

 代码

const int MAX=2147483647;
int maxn=21;
int a[3]={2,5,9};
int dp[maxn+1];
dp[0]=0;
for(int i=1; i<=n; i++)
{
	dp[i]=MAX;
	for(int j=0; j<=2; j++)
	{
		if(i>=a[j]&&dp[i-a[j]]!=MAX)
		{
			if(i>=a[j]&&dp[i-a[j]]+1,dp[i]);
		}
	}
}

---

以上就是本文的全部内容啦！