交付状态转移加记忆化

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

这是这条路线的最终作品。六个函数都在，补全其中的记忆化 fib、填表 fib、打家劫舍、最大子段和，main 一次验完五条：朴素 fib(12) 调用 465 次、记忆化只要 23 次且结果相同；填表 fib(12) 也是 144；爬 10 级 89、打家劫舍 12、最大子段和 6；全负数 [-3,-1,-4] 的最大子段和是 -1；爬楼梯 n=0 是 1、打家劫舍空数组是 0。五条全过输出 验收通过，否则输出 验收失败。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步把边界单独验对拍要拿谁当标准 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long fib_cnt(int n, int& t) {
    t++;
    if (n < 2) return n;
    return fib_cnt(n - 1, t) + fib_cnt(n - 2, t);
}

long long fib_memo(int n, vector<long long>& memo, int& t) {
    t++;
    // TODO: memo[n] 不是 -1 就直接返回它；n 小于 2 返回 n；算出结果先存进 memo[n] 再返回
    return 0;
}

long long fib_tab(int n) {
    // TODO: n < 2 直接返回 n；否则开 n+1 格的表，dp[1] = 1，从 2 填到 n
    return 0;
}

vector<long long> climb(int n) {
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        if (i >= 2) dp[i] += dp[i - 2];
    }
    return dp;
}

vector<int> rob(const vector<int>& a) {
    vector<int> dp(a.size() + 1, 0);
    // TODO: 有第一家就 dp[1] = a[0]；从 2 填到 a.size()：不偷取 dp[i-1]，偷取 dp[i-2] + a[i-1]
    return dp;
}

int max_sub(const vector<int>& a) {
    // TODO: best、cur 都从 a[0] 起；从下标 1 开始 cur = max(a[i], cur + a[i])，再更新 best
    return 0;
}

int main() {
    vector<bool> checks;
    int a = 0, b = 0;
    vector<long long> memo(64, -1);
    long long x = fib_cnt(12, a);
    long long y = fib_memo(12, memo, b);
    checks.push_back(a == 465 && b == 23 && x == y);
    checks.push_back(fib_tab(12) == 144 && fib_tab(12) == x);
    checks.push_back(climb(10)[10] == 89 && rob({2, 7, 9, 3, 1}).back() == 12 && max_sub({-2, 1, -3, 4, -1, 2, 1, -5, 4}) == 6);
    checks.push_back(max_sub({-3, -1, -4}) == -1);
    checks.push_back(climb(0)[0] == 1 && rob({}).back() == 0);
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

交付状态转移加记忆化

更多题目

全部评论