HDU 1284 钱币兑换问题(递归)

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1284

代码:

#define MaxSize 32768
 
int cnt[MaxSize][4];
 
int partition(int n, int m)
{
    if (cnt[n][m] > 0)
    {
        return cnt[n][m];
    }
    if (1 > m || 1 > n)
    {
        return 0;
    }
    if (1 == m || 1 == n)
    {
        return 1;
    }
    if (n < m)
    {
        return partition(n, n);
    }
    if (n == m)
    {
        return m;
    }
    return cnt[n][m] = partition(n, m - 1) + partition(n - m, m);
}
 
int main()
{
    int num;
    while (EOF != scanf("%d", &num))
    {
        printf("%d\n", partition(num, 3));
    }
    return 0;
}

分析:

第一种是通过递归实现:
今天刚从《妙趣横生的算法》看到整数的划分数的递归算法。
以下是归纳出来的递归函数式:
设标记P(n, m)表示正整数n的所有不同划分中,最大加数不大于m的划分个数。
               [  1             m = 1;
P(n, m) = [  P(n, n)          n < m;
               [  1 + P(n, n-1)       n = m;
               [  P(n, m-1) + P(n-m, m)  n > m > 1.
由于本题已经对m作出限制(m ≤3),所以要对上诉递归函数式作些修改
P(n, m) = 1 + P(n, n-1)  n = m;  修改为  P(n, m) = m  n = m;  因为m = 1,只有一种方案;m = 2, 2种;m = 3,3种。
相关文章
相关标签/搜索