image.png
明显的递归问题。
分析：
边界条件： n = 1，返回1
状态转移方程：
f(n) = f(1) + f(2) + ... + f(n / 2) + 1
image.png
使用动态规划减少重复计算：
image.png
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int dp[1002];
// 动态规划
int total_numbers(int n) {
if (n == 1) return 1;
int sum = 1;
if (dp[n]) return dp[n];
for (int i = 1; i <= n / 2; i++) {
sum += total_numbers(i);
}
return dp[n] = sum;
}
// 非动态规划
int total_numbers_2(int n) {
if (n == 1) return 1;
int sum = 1;
for (int i = 1; i <= n / 2; i++) {
sum += total_numbers(i);
}
return sum;
}
void solve(int n) {
printf("%d", total_numbers(n));
// printf("%d", total_numbers_2(n));
}
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
solve(n);
return 0;
}
image.png
