Note / 8.19 动态规划
2023-08-19 16:17:01
发布于：广东
2阅读
0回复
0点赞
动态规划(Dynamic programming)
答案都存在数组里 想要谁输出谁
动态转移方程：a[i]与a[i-1]的关系
// eg.T2914.凑零钱
dp[0,0,0,0,0,0,0,0,0,0,0,0,0]
0,1,2,3,4,5,6,7,8,9....
if(i<5) dp[i]=dp[i-1]+1; //只能给单张1r
else if(i<11) dp[i] = min(dp[i-5]+1,dp[i-1]+1); // 5r 与 1r 纸币的规划
else dp[i] = min(min(dp[i-11]+1,dp[i-5]+1),dp[i-1]+1) // 三种纸币的规划
完整demo of T2914
#include<iostream>
using namespace std;
int dp[100005];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i){ //规划1-n的最优解
if(i<5) dp[i] = dp[i-1]+1;
else if(i<11) dp[i]=min(dp[i-5]+1,dp[i-1]+1);
else dp[i]=min(min(dp[i-11]+1,dp[i-5]+1),dp[i-1]+1);
}
cout<<dp[n];
return 0;
}
T2117 跟踢cheer有点不一样 更清晰
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
int main(){
int m,n;
cin>>m>>n;
dp[1][1]=1;
for(int i=1;i<=m;++i){
dp[i][1]=1;
}
for(int i=1;i<=n;++i){
dp[1][i]=1;
}
for(int i=2;i<=m;++i){
for(int j=2;j<=n;++j){
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
cout<<dp[m][n];
return 0;
}
这里空空如也
有帮助，赞一个