首页 > 代码库 > 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