整數(shù)劃分問(wèn)題是把一個(gè)正整數(shù) N 拆分成一組數(shù)，并且使這組數(shù)相加等于 N 的問(wèn)題.
比如:
6
5 + 1
4 + 2, 4 + 1 + 1
3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

這里，5+1和1+5是同一種分法。
這里探討整數(shù)劃分的可行解的數(shù)目。
問(wèn)題求解：
首先假設(shè)正整數(shù)n拆分成k個(gè)數(shù)(不允許有0)，用f(n,k)表示正整數(shù)n拆分成k個(gè)數(shù)的可行拆分種類的數(shù)目。
那么
f(n,n)表示n拆分成n個(gè)數(shù)(即只有n個(gè)1)，顯然f(n,n) = 1
然后，可以按照這k份中是否有一份的數(shù)為1分成兩類：
1)   這k份中沒(méi)有1份含1的：那么可以在n中拿出k個(gè)"1"出來(lái)，分到k份中，再將剩下n-k分到k份中，于是這時(shí)有
f(n,k) = f(n-k,k)
2)  這k份中至少有一份含有1：首先在n中拿1個(gè)"1"出來(lái)，再將剩下n-1分到k-1份中，于是這時(shí)有：f(n,k) = f(n-1,k-1)

綜合起來(lái)就是：
f(n,n) = 1
f(n,k) = f(n-k,k) + f(n-1,k-1)
這兩個(gè)遞歸式可以使用動(dòng)態(tài)規(guī)劃求解。

題目鏈接：
http://poj.org/problem?id=1283
題解：直接按照整數(shù)劃分來(lái)解
代碼：
 

代碼：

import java.util.Scanner;
import java.util.Arrays;

public class Main 
{
    private static long [][]dp = new long[32][32];
    
    private static long Test(int _n,int _k)
    {
        if(_n < _k)
            return 0;
        for(int i = 0; i <= _n; ++i)
            Arrays.fill(dp[i],0);
        
        for(int i = 1; i <= _n; ++i)
        {
            dp[i][i] = 1;
        }
        
        for(int i = 2; i <= _n; ++i)
        {
            for(int j = 1; j <= _k; ++j)
            {
                dp[i][j] = dp[i-1][j-1];
                if(i - j > 0)
                    dp[i][j] += dp[i-j][j];
            }
        }
        
        return dp[_n][_k];
    }
    
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        int testcase = in.nextInt();
        int m,n;
        for(int i =0; i < testcase; ++i)
        {
            m = in.nextInt();
            n = in.nextInt();
            System.out.println(Test(m+n,n));
        }
    }
}