Poj Solution 1664

http://poj.org/problem?id=1664

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 *
 *poj1664
 * f(m, n) = f(m-n, n) + f(m, n-1)
 * f(m, n): ��m��ƻ��ŵ�n�������еķ�����
 * f(m, n-1): ��m��ƻ��ŵ�n-1�������еķ�����(����������һ�������)
 * f(m-n, n): ��m��ƻ��ŵ�n��������,����ÿ�������ж���ƻ��(����n���4,��m-n��ź���,Ȼ��ÿ�����ӷ�һ��)
 * @author NC
 */
public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        if (scan.hasNext()) {
            int n = scan.nextInt();
            for (int i = 0; i < n; i++) {
                int a = scan.nextInt();
                int b = scan.nextInt();
                System.out.println(f(a, b));
            }
        }
    }

    static int f(int m, int n) {
        /* ��Щ���Ӳ���ƻ���Ѱ���f(m, n - 1)�У�����0*/
        if (m < 0) {
            return 0;
        }
        /* �պ�ÿ�����ӷ�1��ֻ��һ����� */
        if (m == 0) {
            return 1;
        }
        /* ֻ��1�����ӿ��Էţ�Ҳֻ��ȫ��������һ����� */
        if (n == 1) {
            return 1;
        }
        /* n�����������ٶ���1�� + ֻ����n-1�������� */
        return f(m - n, n) + f(m, n - 1);
    }
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *