NOIp2001 数的计算dfs,算法,动态规划Sakuracode的博客-

【递推||回溯】NOIp2001普及组 数的计算

题目链接

第一次看竟然没有思路，看来还是我太菜了
  这题可以用递归（回溯）做，也可以用递推做。但是思路都是一样的。这里的重点是当你在左边填了一个数后，下一次填数是以你填的这个数为基础的，而不是之前的原数。
  现在，对于一个数n，我在他的左边可以填1…n/2（注意这里一半也能填），那么填完后就变成了求我填的这个数有几种拓展的方法数，因此就分解成了规模更小的几个子问题。
  光说可能不一定能理解，蒟蒻就拿给的样例来解释一下思路
  输入n = 6，那么6左边填完后可能是16，26，36吧，1，2，3就对应了1…n/2吧。所以n = 6就被转换成了n = 1，n = 2，n = 3这三种方法的情况之和。对于n = 1、2、3的情况，我们还以相同的方式去求，最后就能求出答案。
  说白了并不难（毕竟只是道橙题），下面给出DFS（回溯）的代码：

//DFS版：注意：会TLE #include<iostream> #include<cstdio> int f(int); using namespace std; int n; int main(){  ios::sync_with_stdio(false);  cin >> n;  cout << f(n) << endl; return 0; } int f(int n){ //n的左边可以填1 ~ n/2 int cnt = 1; //注意，n本身也算一种，所以初始为1  for(int i = 1;i <= n/2;i++){   cnt += f(i); } return cnt; } 

  虽然n最大是1000，看似不大，但是dfs会超时。因为我们算了很多次参数重复的情况。当子问题重复时，我们可以用记忆化搜索的方式去改进，但是这题记忆化和递推区别不大，所以我们再用递推的方式去改写代码。这题改成递推就是算出一个就保存，这样以后用到的时候可以直接用，而不是像dfs再算一遍（好像这个各位大佬早就明白了？/捂脸）
  递推版本的AC代码如下：

#include<iostream> #include<cstdio> using namespace std; int n,ans[1010]; //ans[i]是i所能拓展出的个数，那么ans[n]就是答案  int main(){  ios::sync_with_stdio(false);    cin >> n;  ans[1] = 1; for(int i = 2;i <= n;i++){   ans[i] = 1; //自己算一种  for(int j = 1;j*2 <= i;j++){    ans[i] += ans[j]; } }  cout << ans[n] << endl; return 0; } 

（又AC了题单的一道题呢）

蒟蒻发文，欢迎各位大佬多多提建议~