动态规划解题套路框架

动态规划解题套路框架

另外！！！# define maxn 100005最好多5个

509.斐波那契数
322.零钱兑换

斐波那契数

#include <iostream> #include<bits/stdc++.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; #define maxn 100000 int mem[maxn]={0};int dp(int n) {if(n==1||n==2){mem[n]=1;return 1;}if(mem[n]!=0){return mem[n];}mem[n]=dp(n-1)+dp(n-2);///确实好久不写了，这里一定要用函数 return mem[n];}int main(int argc, char** argv) {cout<<dp(8);return 0; }

零钱兑换

#include <iostream> #include<bits/stdc++.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; #define maxn 10000 int coin[3]={1,2,5}; int coinnum=3; ///int mem[maxn]={maxn};这句话是错的，初始不赋0的话只能赋第一个 int mem[maxn]={0}; int dp(int n)///还剩n元 {if(n==0)///小于零的一会在选择上踢出去 {return 0;}if(mem[n]!=0){return mem[n];}int res=maxn;for(int i=0;i<coinnum;i++){if(n-coin[i]<0){continue;}res=min(res,dp(n-coin[i])+1);}mem[n]=res;return mem[n];}int main(int argc, char** argv) {cout<<dp(11);return 0; }

错误代码：：：！！！！！！

#include <iostream> #include<bits/stdc++.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; #define maxn 10005 int coin[3]={1,2,5}; int coinnum=3; ///int mem[maxn]={maxn};这句话是错的，初始只能赋0 int mem[maxn]={0}; int dp(int n)///还剩n元 {if(n==0)///小于零的一会在选择上踢出去 {return 0;}if(mem[n]!=maxn){return mem[n];}for(int i=0;i<coinnum;i++){if(n-coin[i]<0){continue;}mem[n]=min(mem[n],dp(n-coin[i])+1);}return mem[n];}int main(int argc, char** argv) {for(int i=0;i<=11;i++)//这里写错成了没有等号，结果一调mem【11】就不相同，为0{mem[i]=maxn;}cout<<dp(11);return 0; }

总结

以上是生活随笔为你收集整理的动态规划解题套路框架的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。