07 洛谷 P1028 数的计算（递归+DP）

题目链接

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