首页 > 代码库 > dp洋洋散散的知识+code
dp洋洋散散的知识+code
/*在数轴上有0-N的位置从0出发每次可以向右走223233步*/// 1 总共的方案数f[i]=f[i-2]+f[i-23]+f[i-233]; f[0]=1; for (int a=1;a<=n;a++) { if (a>=2) f[a]+=f[a-2]; if (a>=23) f[a]+=f[a-23]; if (a>=233) f[a]+=f[a-233]; } printf("%d\n",f[n]);// 2 考虑恰好t次到达时//dp 题 可以考虑 每多一个条件 数组就多一维;所以,开二维数组//f[i][j] 表示 用 j 步走了i种方案f[i][j]=f[i-2][j-1]+f[i-23][j-1]+f[i-233][j-1]; f[0][0]=1; for (int a=1;a<=n;a++) for (int b=1;b<=t;b++) { if (a>=2) f[a][b]+=f[a-2][b-1]; if (a>=23) f[a][b]+=f[a-23][b-1]; if (a>=233) f[a][b]+=f[a-233][b-1]; } printf("%d\n",f[n][t]); int ans=0; for (int a=0;a<=t;a++) ans+=f[n][a]; printf("%d\n",ans);// 3 考虑小于t次//将f[n][1]+f[n][2]+....f[n][t];//考虑最多走r步233//so 要再加一维,变成三维数组//f[i][j][k] 表示走到 i点,公用j步,走233用了k步 f[i][j][k]=f[i-2][j-1][k]+ f[i-23][j-1][k]+ f[i-233][j-1][k-1];/*(N,M)的方格图从(0,0)开始只能朝右或上走问走到(N,M)的方案数*/ //将每个点的左边点和下边点相加f[n][m]=f[n-1][m]+f[n][m-1];//考虑有k个点(x,y)不能走//定义布尔数组记录每个不能坐的点 每次设f[x][y]=0,并加以判断;//2.考虑每个坑只能掉一次:if(不是坑)F[i][j][k]=f[i-1][j][k]+f[i][j-1][k];else if(是坑)F[i][j][1]=f[i-1][j][0]-f[i][j-1][0];#include<iostream>using namespace std;int main() { int n,i,j,a[101][101]; cin>>n; for (i=1; i<=n; i++) for (j=1; j<=i; j++) cin>>a[i][j]; //输入数字三角形的值 for (i=n-1; i>=1; i--) for (j=1; j<=i; j++) { if (a[i+1][j]>=a[i+1][j+1]) a[i][j]+=a[i+1][j]; //路径选择 else a[i][j]+=a[i+1][j+1]; } cout<<a[1][1]<<endl;} int fib(int a){ if (!a) return 0; if (a==1) return 1; if (g[a]) return f[a]; g[a]=true; f[a]=fib(a-1)+fib(a-2); return f[a];} 数字三角形问题,使得答案对p取模最大?F[i][j][k] 表示走到第i行第j列 使得答案模p是否可行F[i][j][k]=f[i+1][j][k-v[i][j]]OrF[i+1][j+1][k-v[i][j]]**********代码: for (int a=1;a<=n;a++) f[n][a][v[n][a]%p]=true; for (int a=n-1;a>=1;a--) for (int b=1;b<=a;b++) for (int c=0;c<p;c++) f[a][b][c]= f[a+1][b][(c-v[a][b]+p)%p] || f[a+1][b+1][(c-v[a][b]+p)%p]; int ans; for (int a=p-1;a>=0;a--) if (f[1][1][a]) { ans=a; break; }//***********区间DP******** /*合并石子每次选择相邻两堆代价为两堆石子和问最小总代价(第一层for循环一定要正着写)因为后一层循环需要前一层循环的数据 */F[l][r]=min(f[l][k]+f[k+1][r]+sum[l][r])/*矩阵乘法自定义顺序使得运算次数最少*///F[i][j] 表示搞定[I,j]的最小代价F[i][j] = min(f[i][k]+f[k][j+1]+cost(I,k,j))
dp洋洋散散的知识+code
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。