图片说明
图片说明



题意及思路

题意：略。
思路：给出一个例子，😄对于4来说，4的左边可以加上1或者2，这是满足题意的。同理，2的左边可以加上1，1的左边不可以加了。😉emmm，可以看出，2能产生的数应该是等于12 + 2，1能产生的数是1。而4能产生的数是14、24、124，最后还有本身4，共产生了4个数。😕不难得出，，其中 j 是所有不超过 i/2 的所有数。数组 q 存储的是当前数能产生的个数，最后+1代表加上本身。


代码 

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3+5;
int q[N];

int main(){  std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;    for(int i=1;i<=n;i++){
        for(int j=1;j<=i/2;j++){
	    q[i] += q[j];
        }
	q[i]++;
    }
    cout << q[n] << endl;
    return 0;
}



题目标签

  • 递归
  • 递推