动态规划（DP）_dp动态规划

动态规划简单的来说：利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。

一、定义:

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
基本思想与策略编辑:
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

简单的说，动态规划算法与分治法类似，其基本思想是将求解问题分解成若干个子问题。

---百度百科

二、执行过程：

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

三、适用情况：

采用动态规划一般有三个性质：

1、最优化原理：问题的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。即将一个大问题分解成小问题，而每个小问题的解也必须是最优的。

注意：以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

2、无后效性：某状态以后的过程不会影响曾经的状态。仅仅与当前状态有关。

3、有重叠子问题：子问题之间是不独立的，即一个子问题可能在下次决策中被多次使用。例如在递归算法中，有些数分解的子问题已经被多次计算，而这种性质被称为重叠子问题。

注意：虽然该性质不是动态规划使用的必要条件，但若没有这条性质，则动态规划算法与其他算法基本没有区别，无法突出动态规划是以空间换取时间的算法。而在动态规划中一般将子问题的解保存在表格中，也可以理解为缓存。

四、求解的基本步骤

• 状态定义： 每个状态的决策，存放每个状态的变量
• 状态转移方程： 当前状态与上一个状态之间的关系
• 初始状态： 初始的状态或者边界条件

五、以斐波那契数列引入

1、递归法求n为50的值

long long fib(int n)
{
	if(n<=2)
		return 1;
	return f(n-1)+f(n-2);
}
for(int n = 1;n<50;n++)
		std::cout<<f(n)<<std::endl;

 我们可以发现直接使用递归，当数字稍微一大时计算时间显著上升。且该算法时间复杂度为O(2`n)。以f(6)为例，我们明显可以发现在递归时，有重复计算。采用动态规划优化

 2、动态规划

• 状态定义：设dp[i]为数列的第i个值
• 状态转移方程：寻找每个子问题的公共问题，即为dp[i] = dp[i-1]+dp[i-2]对应斐波那契数列的定义。

初始状态：dp[0] = 1  dp[1]= 1

    long long dp[50]; 
	dp[0] = 1;
	dp[1] = 1;
	for(int n = 2;n<50;n++)
	{
		dp[n] = dp[n-1]+dp[n-2];
		std::cout<<n<<": "<<dp[n]<<std::endl;
	}

或用map实现，每次查询，如果存在直接取出使用，否则进行添加。

std::map<LL,LL> M;
LL fib(int n)
{
	if(n<=2)
		return 1;
	if(M.count(n))
		return M[n];
	else
		M[n] = fib(n-1)+fib(n-2);
	return fib(n-1)+fib(n-2);
}

或使用滑动窗口来重复利用前三个值(第一项，第二项，总和)。对每次的下标进行对3取余

LL dp[3];
dp[1] = 1;
dp[2] = 1;
for(int i = 3;i<=n;i++)
{
	dp[i%3] = dp[(i-1)%3]+dp[(i-2)%3];
	std::cout<<i<<": "<<dp[i%3]<<std::endl;
}

使用动态规划我们可以发现，时间复杂度明显下降，但空间复杂度提高，并且使用动态规划关键点在于写出状态转移方程。

背包问题

问题描述：

动态规划分析：

首先我们直观感受是利用穷举法来保存当背包容量依次增加的时候，该物品能否加入到背包里（依顺序取），所以我们要记录每次物品在背包里面的状态，如果装不进去，则记为0，否则记该物品的价值。显然的我们需要定义二维数组（物品编号，背包容量）。

但是题目要求的是最大值，如果一次只能装入一个物品，那好说直接比较就行，但背包可能存在可以装入2个或更多物品的状态。所以我们采用动态规划的思想，将大问题划分为子问题，求当背包重量依次增加时，哪几个物品（如1、2或3,4或1,3）装在一起的最大值。进而求得总体的最大值。

• 状态定义：利用枚举法来判断该物品是否可以装入背包，能装入则增加价值，所以定义二维数组dp[i][j]记录当第i件物品，背包容量为j时的价值。关键在于每个物品都有两种状态（装或不装）
• 初始状态和边界条件：当物品件数为0，或背包容量为0时，其价值都为0。
• 状态转移方程：这是此题的关键点，分析如下：

我们记f(n,w)，可取的物品数为n，背包剩余容量为w。以f(4,8)说明：

阶段一：当f(4,8)，n为4，w为8时，为当前有4件物品可以选择，背包剩余量为8，如果装第四件物品，进行比较发现(8>5)可以装，将第4件物品装入，价值为8，同时减少背包剩余量，或者不装第4个，选择装第三个。

阶段二：此时装入第4件物品的状态为f(3,3)，我们继续选择装第三件物品，但（4>3）无法装入第三个物品，只能选择第二个物品。状态为f(2,3)

阶段三：f(2,3)，继续选择装入第2件物品，继续比较（3==3）将第2件物品装入。价值为12。此时状态为f(1,0)。已经达到临界条件，无法装入物品。

题目要求价值最大，假设当前物品数为2(n=2)，所以我们还要比较的当前装入物品(n=2)价值与上一个装入物品(n=1)价值的大小，取最大的价值。更直白的来讲：假如有2件物品a,b，假设只装第一件物品a和只装第二件物品b的价值已经纪录，而下来我们就要比较当可以装两件物品时，到底是只装a价值大，还是只装b价值大，还是a,b都装价值大，但如果两个都装背包容量可能超过价值为0，所以在这种情况下取最大的，即满足子问题最优解的性质。

 

我们还可以发现，当我们从物品1到物品4开始枚举时已经纪录了物品1各个状态的价值，所以在f(0,1)的时，直接取值（f(0,1)=0）使用即可。满足有重叠子问题性质。

综上分析：状态转移方程为 

 各个状态表格如下：

 综上实现代码如下：

定义物品价值数组V[5]，物品重量数组W[5]，纪录各状态数组dp[5][9]。

注意：虽然物品数量为4，但数组开辟个数为5，这是因为有边界条件，即物品为0的时候。

int f[5][9] = {0};
int w[5] = {0,2,3,4,5};//重量
int v[5] = {0,3,4,5,8};//价值
int main()
{
	int i,j;//i为物品  j为背包重量
	memset(f,0,sizeof(f));
	for(int i = 1;i<5;i++)
	{
		for(int j = 1;j<9;j++)
		{
			if(w[i]>j)
				f[i][j] = f[i-1][j];
			else
				f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
			}
		}
	}
	for(int i = 0;i<5;i++)
	{
		cout<<i<<":";
		for(int j = 0;j<9;j++)
			printf("%d  ",f[i][j]);
		cout<<endl;
	}
	return 0;
}

 循环每个阶段的背包剩余量与物品剩余量，利用二维数组纪录最大价值，下标为物品编号与此时的背包容量。

我们可以总结为：如果装不下，就把上一个物品装进去，如果可以装进去，取价值，减数量，减容量了，再试着装上一个物品背包容量减后的状态。再进行比较保证上一个物品装入与本次物品装入价值都为最大值。