题解：P1028 [NOIP 2001 普及组] 数的计算

· · 题解

最基础的DP

第一眼看到这题其实很容易想到dfs，但是O(2^N)很明显过不了

这时候，我们就需要引进一个新的概念

动态规划

简单的来说，就是优化到极致的搜索。

在研究这个问题之前，我们来讨论一下，为啥搜索这么慢

因为过于多的重复搜索（就是所谓的殊途同归）

我们发现要优化它很简单，居然很多重复搜索，那我开一个数组来维护状态，那么下一次遍历时，直接调用。 当然我们要满足一件事我在第 i 步时的选择，不会影响到 i 步之后（无后效性）

那么这题就呼之欲出了，我们选择从后往前递推设f_i为当前数列第一个数为 i 的数列个数。

那么

f_n-1 = \sum_{i = 1}^{n} \frac{n}{2}

代码：

#include <bits/stdc++.h>
using namespace std;
int n,f[1005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=i/2;j>=1;j--)f[i]+=f[j];
    }
    cout<<f[n];
    return 0;
}

时间复杂度O(N^2),空间复杂度O(N),可以通过此题。