记忆化递归

洛谷新手村P1028

题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数nn):

先输入一个自然数nn(n le 1000n≤1000),然后对此自然数按照如下方法进行处理:

1. 不作任何处理;

2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入格式

11个自然数nn(n le 1000n≤1000)

输出格式

11个整数，表示具有该性质数的个数。

输入输出样例

输入 #1复制

6

输出 #1复制

6

#include<iostream>

using namespace std;
int a[1005];
int count(int n)
{
    if(n==1)return 0;
    long long ans=0;
    if(a[n]==0)//如果没有计算过这个数，计算并储存在a[n]中
    {
        for(int i=1;i<n;i++)
        if(i*2<n||i*2==n)
            ans+=count(i)+1;
    return a[n]=ans;
    }
    else//计算过这个数的话直接返回这个数对应值
        return a[n];
}

int main ()
{
    int n;
    cin>>n;
    cout<<count(n)+1;
    return 0;
}