鸡蛋的硬度DP

题目

原题链接

问题描述

鸡蛋硬度定义：如果一只母鸡的鸡蛋从高楼的第$a$层摔下来没摔破，但是从$a1$层摔下来时摔破了，那么就说这只母鸡的鸡蛋的硬度是$a$。

现给定楼层$n$，硬度相同的$m$个鸡蛋，问采取最优策略在最坏情况下需要的扔鸡蛋次数。
对每组输入数据，你可以假定鸡蛋的硬度在$0$至$n$之间，即在$n1$层扔鸡蛋一定会碎。

分析

我们以$dp[i][j]$表示硬度位于$[0,i]$，$j$个鸡蛋的情况下的最优解，我们看能不能把这个问题进行分解。

步骤一：确定状态
步骤二：确定状态转移方程
步骤三：确定边界情况和初始条件
步骤四：确定计算顺序

动态规划求解问题的基本条件：
1）无后效性： 动态规划要求已经求解的子问题不受后续阶段的影响，以保证对每一阶段的计算能够按顺序、不重复地执行。
2）最优子结构性质： 在动态规划算法求解问题的过程中，下一阶段的解应该能由前面各阶段子问题的最优解导出。

对于需要求解的$dp[i][j]$，假设我们在楼层$k(1\le k\le i)$扔下了一个鸡蛋，鸡蛋只有两种结局：摔碎OR没事。

如果鸡蛋碎了，说明鸡蛋的硬度在$[1,k-1]$，此时鸡蛋的个数为$j-1$那么我们接下来的问题就是需要求$dp[k-1][j-1]$；
如果鸡蛋没碎，说明鸡蛋的硬度在$[k,i]$，鸡蛋个数为$j$，这种情况其实等效于$dp[i-k][j]$，即将鸡蛋硬度视为$[0,i-k]$.

由上面的分析我们可以看出这个问题满足DP的条件，下一步就是确定状态转移方程。

依然是在楼层$k$扔了一个鸡蛋后，此时的$dp[i][j]$应该是什么值呢？
$dp[i][j]=min(dp[i][j],1max(dp[k-1][j-1],dp[i-k][j]))$
内部嵌套的$max$指的是取其中最坏的情况，它的实际意义就是指通过在$k$层扔一次鸡蛋，问题得到简化，两个可能的子状态对应着两种情况，取子状态中的最大值作为最坏情况。
外部的$min$指的是即便是在最坏情况下，我们仍然选择最小值作为我们的最优解。
当然了，这仅仅是在楼层$k$扔下的讨论，我们需要讨论在$[1,i]$每一层扔下的情况。

for(int k=1;k<=i;k  ){
	dp[i][j]=min(dp[i][j],1 max(dp[k-1][j-1],dp[i-k][j]));
}

接下来我们的任务是确定边界条件和初始化，在上面的分解中最小的状态也就是$dp[1][j]$跟$dp[i][1]$
$dp[1][j]$：硬度为$[0,1]$，$j$个鸡蛋，那么$dp[1][j]$就等于1，一次就可确定；
$dp[i][1]$：硬度为$[0,i]$，$1$个鸡蛋，那么$dp[i][1]$就等于$i$，自下往上，逐个尝试，最坏要$i$次；
至于其余的$dp[i][j]$，我们可以置为无穷大，递推中会对其逐个更新。

代码

#include<bits/stdc  .h>
using namespace std;
typedef long long ll;
ll n,m;
ll dp[105][15];
int main(){
	for(int i=1;i<=100;i  )dp[i][1]=i;
	for(int i=1;i<=10;i  )dp[1][i]=1;
	for(int i=2;i<=100;i  ){
		for(int j=2;j<=10;j  ){
			dp[i][j]=INT_MAX;
		}
	}
	for(int i=2;i<=100;i  ){
		for(int j=2;j<=10;j  ){
			for(int k=1;k<=i;k  ){
				dp[i][j]=min(dp[i][j],1 max(dp[k-1][j-1],dp[i-k][j]));
			}
		}
	}
	while(cin>>n>>m&&n&&m){
		cout<<dp[n][m]<<endl;
	}
}

这篇好文章是转载于：学新通技术网