04-数的计算

题目：
给出正整数 n，要求按如下方式构造数列：
1.只有一个数 n 的数列是一个合法的数列。
2.在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。
请你求出，一共有多少个合法的数列。两个合法数列a,b不同当且仅当两数列长度不同或存在一个正整数i≤∣a∣,使得
a i !=b i
​输入格式
输入只有一行一个整数，表示 n。
输出格式
输出一行一个整数，表示合法的数列个数

代码：
//20

include

using namespace std;

int n;
int dp[1001];

int dfs(int n){
if(n == 1) {
return dp[n];
}
if(dp[n] > 1) {
return dp[n];
}
for(int i = 1; i <= n/2; i++){
dp[n] += dfs(i);
}
return dp[n];
}

int main(){
cin>>n;
for(int i = 0; i <= n; i++){
dp[i] = 1;
}
cout<<dfs(n);
return 0;
}
递归式：f[i]=f[1]+f[2]+f[3]+…+f[i/2]+1

分析以及优化：
eg: n = 6
1>计算f(6) 未被计算 进入循环
2>计算f(1) 到达最底层 计算 退出循环
3>计算f(2) 未被计算 进入循环
3.1>计算f(1) 到达最底层 计算 退出循环
4>计算f(3) 未被计算 进入循环
4.1>计算f(1)到达最底层 计算 退出循环
现象：f(1)被重复遍历 虽然并未进行计算，但多次遍历仍然耗费时间
整体上看：遍历了三遍f(1) 返回计算f(2) f(3) f(6)

优化：空间换时间
递推公式可以优化为：
f(n)=SUM(n/2)+1,SUM(i)=SUM(i−1)+f(i)
代码：

include

using namespace std;

int f[1005], sum[505];

int F(int i); int Sum(int i);

int main(){
int n; cin>>n;
f[1] = sum[1] = 1;
cout<<F(n);
}

int F(int i){
if(f[i]) return f[i]; //剪枝
return f[i] = Sum(i/2) + 1; //利用赋值，记忆
}

int Sum(int i){
if(sum[i]) return sum[i]; //剪枝
return sum[i] = Sum(i - 1) + F(i); //利用赋值，记忆
}
未优化的代码只记忆了每个数的序列数量
而优化后的代码 一个数组记忆每个数的序列数量 一个数组记忆前2/n个数序列的和
这样每次计算，不用再求f[1]+f[2]+f[3]+…+f[i/2]
只需要求f(n)=SUM(n/2)+1

eg: n = 6
1.计算f(6) 未定义 计算sum(3) + 1
1.1计算sum(3) sum(3) = sum(2) + f(2)
1.1.1计算sum(2) sum(2) = sum(1) + f(1) 并列 计算f(2) f(2) = sum(1) + 1
1.1.1.1计算sum(1) 已被定义 返回 并列 计算f(1) 已被定义 返回
整体上看 只遍历了一遍f(1) sum(1) 返回计算sum(2) f(2) 再返回计算sum(3)

继续优化—“就地” 在原地修改数据结构或数组，而不使用额外的空间来存储中间结果
f(n)=SUM(n/2)+1,SUM(i)=SUM(i−1)+f(i) 相当于只存储最后计算的f(n)的结果，自下而上计算，每向上以及就覆盖一次原值

include

using namespace std;

int f, sum[505];

int main(){
int n; cin>>n;
for(int i = 1; i <= n/2; i++){
f = sum[i/2] + 1;
sum[i] = f + sum[i - 1];
}
cout<< sum[n/2] + 1;
}