动态规划：划分DP

92 阅读 0 评论 61 点赞

我是靠谱客的博主成就网络，最近开发中收集的这篇文章主要介绍动态规划：划分DP，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

划分型动态规划之数的划分

先贴上2014年10月31日的那份代码，甚至怀念当时在机房YY这道题的场面

高中最快乐的时候。。

#include<iostream>
using namespace std;
int n,k;
int ans;
void make(int a,int t,int d)
{
    if (d==k)
    ans++;
    else
    for(int i=t;i<=a/2;i++)
    make(a-i,i,d+1);
}
int main()
{
    cin>>n>>k;
    ans=0;
    make(n,1,1);
    cout<<ans;
    //while(1);
    return 0;
}

很可爱的一道题

今天的重点是划分型动态规划

所谓的划分，可以说成一种模型吧。我可以把转移方程称为2D/0D么

 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn=205;
 4 const int maxk=10; 
 5 int n,k;
 6 int f[maxn][maxk];
 7 //f[i][j]是指将i划分成j部分的方案数 
 8 int main()
 9 {
10     scanf("%d%d",&n,&k);
11     f[0][0]=1;
12     for(int i=1;i<=n;i++)
13         for(int j=1;j<=k;j++)
14             if(i>=j) f[i][j]=f[i-1][j-1]+f[i-j][j];
15             //有一种情况是分离出一个1，那么剩余的i-1就只能划分成j-1个部分
16             //第二种情况为了不包含1，就先把可能涉及1的情况都排除，也就是i-j
17             //最终结果，可能一直走第一种情况，也可能一直走第二种情况，也可能混着走 
18     printf("%d",f[n][k]);
19     return 0;
20 }