牛客 QQ7 拼凑硬币

Tag: 牛客腾讯题库 Posted on 2022-03-03 16:37:47 Edited on 2022-03-03 17:21:34 Views: 158

概述

https://www.nowcoder.com/practice/2479839aa61e44f39aa3268160650e17

这道题还是挺有意思的,看了别人的评论才搞出来。

动态规划法

n 太大了,1≤n≤10^18,下面的解法超时。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

unordered_map<unsigned long, unordered_map<unsigned long, int>> m;

int helper(unsigned long i, unsigned long n) {
    if (n == 0) return 1;
    if (n < 0) return 0;
    if (m[i].count(n)) return m[i][n];
    unsigned long pow2i = pow(2, i);
    if (pow2i > n) return 0;
    int ans = helper(i+1, n);
    if (n >= pow2i) ans += helper(i+1, n-pow2i);
    if (n >= 2 * pow2i) ans += helper(i+1, n-2*pow2i);
    m[i][n] = ans;
    return ans;
}

int main() {
    unsigned long n; cin >> n;
    cout << helper(0, n);
}

动态规划 + 递归

上面的解法没有利用 2^k 的形式,很明显可以递归。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

unordered_map<unsigned long, int> m;

int helper(unsigned long n) {
    if (n == 0) return 1;
    if (n < 0) return 0;
    if (m.count(n)) return m[n];
    if (n % 2 == 1) {
        m[n] = helper((n - 1) / 2);
    } else {
        m[n] = helper((n - 2) / 2) + helper(n / 2);
    }
    return m[n];
}

int main() {
    unsigned long n; cin >> n;
    cout << helper(n);
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/