牛客 QQ7 拼凑硬币

    
        标签：
        
            牛客腾讯题库
        
    发布于：2022-03-03 16:37:47
    编辑于：2022-03-03 17:21:34
    浏览量：538

概述

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);
}

Links: 牛客-qq07-拼凑硬币