hdu 1284 钱币兑换问题(动态规划)

 

Ac code :

完全背包：

#include<stdio.h>
#include<string.h>
int dp[4][40000];
int main(void)
{
    int i,j,n;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(i=1; i<=3; i++)
    {
        for(j=0; j<32770; j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i][j-i];
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d
",dp[3][n]);
    }
    return 0;
}

完全背包-滚动数组法：

#include<stdio.h>
#include<string.h>
int dp[40000];
int main(void)
{
    int i,j,n;
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(i=1; i<=3; i++)
    {
        for(j=i; j<32770; j++)
        {
            dp[j]+=dp[j-i];
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d
",dp[n]);
    }
    return 0;
}

非背包解法：

#include<stdio.h>
int f(int n)
{
    int sum,i,x=n/3;
    sum=n/3+1;
    for(i=0; i<=x; i++)
    {
        sum+=((n-i*3)>>1);
    }
    return sum;
}
int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d
",f(n));
    }
    return 0;
}

　博文中问题分析图来自：

http://blog.csdn.net/u013480600/article/details/40477769