POJ 3181 DP

题目链接:http://poj.org/problem?id=3181

用 $1..k$ 这 $k$ 种数去凑 $N$,有多少种凑法?

例如 $N = 5, k = 3$:

1+1+1+1+1
2+1+1+1
2+2+1
3+1+1
3+2

思路

定义 $dp[i][j]$ 为 用不超过 $j$ 的数去凑 $i$ 的凑法数量。

可以分为两种情况:

  1. 这些数存在 $j$,则方案数为 $dp[i-j][j]$
  2. 所有数小于 $j$,则方案数为 $dp[i][j-1]$

$$
dp[i][j] = dp[i][j-1] + dp[i-j][j] (i \geq j)
$$

3181.cppview raw
#include <iostream>
#include <stdio.h>
#define maxn 1005
#define maxk 105
using namespace std;

int dp[maxn][maxk], n, k;

int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i <= n; i++)
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j <= k; j++)
dp[0][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = 2; j <= k; j++)
if (i - j >= 0)
dp[i][j] = dp[i][j - 1] + dp[i - j][j];
else
dp[i][j] = dp[i][j - 1];
printf("%d\n", dp[n][k]);
return 0;
}

不过这段代码是通过不了的,因为本题数据范围很大,需要用到高精度计算,Java 代码如下:

Main.javaview raw
import java.util.*;
import java.math.BigInteger;

public class Main {
public static void main(String[] args) {
BigInteger dp[][] = new BigInteger[1005][105];
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
for (int i = 0; i <= n; i++)
dp[i][0] = dp[i][1] = BigInteger.valueOf(1);
for (int j = 0; j <= k; j++)
dp[0][j] = dp[1][j] = BigInteger.valueOf(1);
for (int i = 2; i <= n; i++)
for (int j = 2; j <= k; j++)
if (i - j >= 0)
dp[i][j] = dp[i][j - 1].add(dp[i - j][j]);
else
dp[i][j] = dp[i][j - 1];
System.out.println(dp[n][k]);
}
}