首页 > 代码库 > 相加之和为某个数n,求方法数 ------------ 动态规划的方法

相加之和为某个数n,求方法数 ------------ 动态规划的方法

uva11137 n3可转化为n2(立方和为n的方法数)

/*
ID: neverchanje
PROG:
LANG: C++11
*/
#include<iostream>
#include<cstring>
#include<cstdio>
typedef long long ll;
using namespace std;

int n;
long long d[23][maxn]; //下标<=21 
int main(){
    memset(d,0,sizeof(d));
    d[0][0]=1;
    for(int i=1;i<22;i++)
        for(int j=0;j<=10000;j++){//注意j不能超过10001,否则会出错(不知道怎么回事) 
            if(j-i*i*i>=0) d[i][j] += d[i][j-i*i*i];
            d[i][j] += d[i-1][j];
        }
    while(cin>>n)
        printf("%lld\n",d[21][n]);
    return 0;
}
/*
DESCRIPTION:
d(i,j)为下标不超过i的立方和为j的方法数 
d(i,j) = sum( d(i-1,j-k*i^3) )
答案是d(21,n)  
 
注意:
由于j要从0开始,所以转移方程要有所改变
d(i,j+k*i^3) = sum( d(i-1,j) ) 
*/
View Code

poj2140 (计算和为n的方法数) 其实这道题有更好的方法

/*
ID: neverchanje
PROG:
LANG: C++11
*/

#include<iostream>
using namespace std;

int res=1,N;
 
void dp(int a,int i){ //a<i的情况可排除 
    if(a==i) res++; 
    else if(a>i) 
        dp(a-i,i+1);
}

int main(){
    cin>>N;
    for(int i=1;i<=N/2+1;i++) //i<=n/2+1会漏掉一个解:N本身,所以res初始化为1 
        dp(N,i);
    cout<<res<<endl;
    return 0;
}

/*
DESCRIPTION:
几个连续的数之和为N
可以用dp
dp(a,i)表示以i为开头的,和为a的连续子序列的数量
dp(a,i) = dp(a-i,i+1) (a>=i)
边界:    i<j 都有 dp(i,j)=0;
用记忆化搜素会更高效一些
复杂度应该是O(n*sqrt(n))的,但实际上应该少的多 
*/
View Code

暂时只有这两题,但是方法各不相同,怕混淆,做个笔记