凑钱I
题目
有面额为1、5、10、20、50、100的钞票不限数量，给定正整数n，求刚好凑出n元所需要的最小钞票张数。
思路
根据日常经验，显然可以贪心来做，即尽可能地先选择面额大的钞票。
凑钱II
题目
问题I中钞票的面额变为1、5、11，之前的解法还成立么？
思路
n=15时，贪心的结果是5(15=11+1*4)，但答案显然应该是3(15=5*3)。贪心只考虑了眼前的策略，陷入了局部最优而非全局最优。
暴力枚举所有可行解复杂度过高，n比较大时难以计算。
用f(n)来表示凑出n元所需的最少钞票数量，显然f(0)=0。
考虑选取的最后一张钞票只能是1、5、11，
三种方案分别花费f(n-1)+1、f(n-5)+1、f(n-11)+1，
显然应该选择花费最小的方案，于是我们得到状态转移公式:
f(n) =min(f(n-1)+1,f(n-5)+1,f(n-11)+1)
递归
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int dfs(int n);
int main()
{
int n;
cin>>n;
cout<<dfs(n)<<endl;
return 0;
}
int dfs(int n)
{
if (n==0) return 0;
int cost=INF;
if (n-11>=0) cost=min(cost,dfs(n-11)+1);
if (n-5>=0) cost=min(cost,dfs(n-5)+1);
if (n-1>=0) cost=min(cost,dfs(n-1)+1);
return cost;
}
记忆化搜索(填表法)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e5+10;
const int INF=0x3f3f3f3f;
int dp[MAXN];
int dfs(int n);
int main()
{
int n;
cin>>n;
memset(dp,-1,sizeof dp);
dp[0]=0;
cout<<dfs(n)<<endl;
return 0;
}
int dfs(int n)
{
if (dp[n]!=-1) return dp[n];
int cost=INF;
if (n-11>=0) cost=min(cost,dfs(n-11)+1);
if (n-5>=0) cost=min(cost,dfs(n-5)+1);
if (n-1>=0) cost=min(cost,dfs(n-1)+1);
return dp[n]=cost;
}
递推(刷表法)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e5+10;
int dp[MAXN];
int main()
{
int n;
cin>>n;
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for (int i=1;i<=n;i++) {
if (i-11>=0) dp[i]=min(dp[i],dp[i-11]+1);
if (i-5>=0) dp[i]=min(dp[i],dp[i-5]+1);
if (i-1>=0) dp[i]=min(dp[i],dp[i-1]+1);
}
cout<<dp[n]<<endl;
return 0;
}
动态规划问题的特点
无后效性
最优子结构
重叠子问题
动态规划算法设计
设计状态
转移路径
转移方程
动态规划原理
规划类问题都是在可行解空间内，寻找最优解。
暴搜是枚举所有可行解。
贪心是选取一个特解。
DP是枚举有希望成为答案的解。
DP剪掉了不可能成为最优解的答案，缩小了可行解空间，完成了优化。
最长上升子序列(LIS)
题目
给定长度为n的序列A，求A最长的单调递增子序列(LIS)的长度。
例如{3,2,1,4,7,5,6}的LIS为{3,4,5,6}，长度为4 。
思路
用f(i)表示以a[i]结尾的LIS长度，初始值f(i)=1。
考虑一个小于i的j，如果a[i]>a[j]，则可以把a[i]接在以a[j]结尾的LIS后面，此时得到的LIS长度为f(j)+1，枚举所有j答案取最大值更新即可。
状态转移方程为：
f(i)=max(f(j)+1) | j<i,a[i]>a[j]
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e3+10;
int a[MAXN],dp[MAXN];
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++) {
scanf("%d",a+i);
dp[i]=1;
}
for (int i=1;i<=n;i++) {
for (int j=1;j<i;j++) {
if (a[i]>a[j]) {
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int ans=0;
for (int i=1;i<=n;i++) {
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}
扔鸡蛋
题目
你在一栋100层的楼上，有两个一模一样的鸡蛋。你需要从楼上往下扔鸡蛋来测试鸡蛋硬度。
如果在第 x 层扔下鸡蛋，鸡蛋不碎，那么从第 x-1 层扔鸡蛋也不碎。
如果鸡蛋从第x层扔下去没摔坏，但从第x+1层扔下去摔坏了，则鸡蛋硬度=x。
特别地，如果从第1层扔下去就坏了，则鸡蛋硬度 =0。
如果在最高的第n层扔下去还没摔坏，则鸡蛋硬度=n。
求最坏情况下的最少测试次数。
思路
设f(m,n)表示有m个鸡蛋测试n层楼时最坏情况下的最多需要次数。
只剩一个鸡蛋的时候，为了确保测试成功，只能采用最保守的方法，一层一层往上试，f(1,n)=n。
对于f(m,n)，假设第一次测试在k层，有两种情况：
①鸡蛋没摔坏，则还需要测试n-k层，转化为f(m,n-k)。
②鸡蛋摔坏了不能继续用于测试，则还需要测试k-1层，转化为f(m-1,k-1)。
考虑最坏情况，测试次数取max，即
f(m,n)=max(f(m,n-k), f(m-1,k-1) )+1
枚举所有可能的k值，取最小次数即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXM=50+10;
const int MAXN=(int)1e3+10;
int dp[MAXM][MAXN];
int main()
{
int m,n;
scanf("%d%d",&m,&n);
memset(dp,0x3f,sizeof dp);
for (int i=1;i<=m;i++) {
dp[i][0]=0;
}
for (int i=1;i<=n;i++) {
dp[1][i]=i;
}
for (int i=1;i<=m;i++) {
for (int j=1;j<=n;j++) {
for (int k=1;k<=j;k++) {
dp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1);
}
}
}
printf("%d\n",dp[m][n]);
return 0;
}
风竹曦のBlog 