HDU_1028题解(DP)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1028

题目大意

给你一个数字N，问将N分解成若干个数字的和有几种方法，每个数字都是正数且不超过N
如:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;

思路1：

考虑一个数组dp[n][m]表示将n分解成不超过m的若干个数字有几种方法
如:
dp[4][1]=1即{1,1,1,1}这一种
dp[4][2]=3 {1,1,1,1} {1,1,2} {2,2}
dp[4][3]=4 {1,1,1,1} {1,1,2} {2,2} {1,3}
dp[4][4]=5 {1,1,1,1} {1,1,2} {2,2} {1,3} {4}
考虑状态转移方程分情况讨论:

• 当m>n时，此时dp[n][m]=dp[n][n],因为你分解的数不会大于n这是显然的
• 当m==n时，此时dp[n][m]=dp[n][m-1]+1,这是因为从dp[n][m-1]到dp[n][m]只会多出一种情况，就是将n分解成n本身这一种情况
• 当m<n的时候此时dp[n][m]=dp[n][m-1]+dp[n-m][m],这是因为当分解出来的数中不出现m时,方案数就是dp[n][m-1],当出现m这个数时，剩下的数的和是n-m,然后就是将n-m分解,方案数就是dp[n-m][m]
  初始化当n或m为1时，dp[n][m]=1;

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
// void read(int &x) {
//  char ch = getchar(); x = 0;
//  for (; ch < '0' || ch > '9'; ch = getchar());
//  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
// }
int dp[121][121];
int main()
{
    std::ios::sync_with_stdio(false);
#ifdef test
    freopen("F:\\Desktop\\question\\in.txt", "r", stdin);
#endif
#ifdef ubuntu
    freopen("/home/time/debug/debug/in", "r", stdin);
    freopen("/home/time/debug/debug/out", "w", stdout);
#endif
    int n = 121;
    int i, j;
    wfor(i, 1, 121)
    {
        dp[1][i] = dp[i][1] = 1;
    }
    wfor(i, 2, 121)
    {
        wfor(j, 2, 121)
        {
            if (i == j)
                dp[i][j] = dp[i][j - 1] + 1;
            else if (i < j)
                dp[i][j] = dp[i][i];
            else
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        }
    }
    while (cin >> n)
    {
        cout << dp[n][n] << endl;
    }
    return 0;
}

思路2：

可以将这题当成完全背包来做，相当于有N件物品，每见物品价值从1-n，花费也是从1-n,现在有个容量为n的背包，问装满背包的方案数

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
// void read(int &x) {
//     char ch = getchar(); x = 0;
//     for (; ch < '0' || ch > '9'; ch = getchar());
//     for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
// }
int dp[121];
int main()
{
    std::ios::sync_with_stdio(false);
#ifdef test
    freopen("F:\\Desktop\\question\\in.txt", "r", stdin);
#endif
#ifdef ubuntu
    freopen("/home/time/debug/debug/in", "r", stdin);
    freopen("/home/time/debug/debug/out", "w", stdout);
#endif
    int i, j;
    dp[0] = 1;
    wfor(i, 1, 121)
    {
        wfor(j, i, 121)
        {
            dp[j] = dp[j] + dp[j - i];
        }
    }
    int n;
    while (cin >> n)
    {
        cout << dp[n] << endl;
    }
    return 0;
}