将 JavaScript 函数转换为 C++

Question

我正在研究动态规划问题，并且能够编写 Javascript 解决方案：

function howSum(targetSum,numbers,memo = {}){
    //if the targetSum key already in hashmap,return its value
    if(targetSum in memo) return memo[targetSum]; 

    if(targetSum == 0) return [];
    if(targetSum < 0) return null;

    for(let num of numbers){
        let aWay = howSum(targetSum-num,numbers,memo);
        if(aWay !== null){
            memo[targetSum] = [...aWay,num];
            return memo[targetSum];
        }
    }

    //no way to generate the targetSum using any elements of input array
    memo[targetSum] = null;
    return null;
}

现在我在考虑如何将其转换为 CPP 代码。我将不得不为 memo 对象使用对 unordered map 的引用。

但是我应该如何 return 设置 empty array 和 null 值作为基本条件？我应该 return 一个 array pointer 和realloc 它在插入元素时？那不就是一种 C 编程方式吗？另外，我应该如何在 C++ 中将 default parameter 传递给 memo 无序映射？目前我已经重载了创建备忘录无序映射并传递其 reference.[=22= 的函数]

任何指导将不胜感激，因为我可以解决未来的问题。

Answer 1

这是我的看法：

#include <optional>
#include <vector>
#include <unordered_map>

using Nums = std::vector<int>;
using OptNums = std::optional<Nums>;

namespace detail {

using Memo = std::unordered_map<int, OptNum>>;

OptNums const & howSum(int targetSum, Nums const & numbers, Memo & memo) {
    if (auto iter = memo.find(targetSum); iter != memo.end()) {
        return iter->second; // elements are std::pair<int, OptNums>
    }
    auto & cached = memo[targetSum]; // create an empty optional in the map

    if (targetSum == 0) {
        cached.emplace(); // create an empty Nums in the optional
    }
    else if (targetSum > 0) {
        for (int num : numbers) {
            if (auto const & aWay = howSum(targetSum-num, numbers, memo)) {
                cached = aWay;           // copy vector into optional
                cached->push_back(num); 
            }
        }
    }
    return cached;
}
} // detail

std::optional<Nums> howSum(int targetSum, Nums const & numbers) {
    detail::Memo memo;
    return detail::howSum(targetSum, numbers, memo);
}

一些评论：

使用两个函数，一个创建备忘录并将其传递给真正的实现函数是一个很好的模式。它使面向用户的界面变得干净。
“detail”命名空间只是一个名称，没有神奇的含义，但通常用于指示实现细节。
在实现中，我returnreferences来一个optional。这是一种优化，可避免在算法从递归展开的每次调用中复制 return 向量。然而，这确实需要一些小心，因为您必须小心 return 对将超过本地范围的对象的引用（因此没有 returning std::nullopt，或者引用绑定到临时例如，可选的。）这也是为什么我总是在备忘录对象中创建元素——即使在否定的情况下——所以我可以 return 安全地引用它。请注意，应用于 unordered_map 的 operator[] 将在元素不存在时创建该元素，而 find 则不会。
由于由 detail 函数编辑的引用 return 的生命周期仅与调用方声明的备忘录一样长，因此调用方本身必须 return可选它返回，以确保数据在函数调用的清理期间不被破坏。请注意，它不是 return 参考。
此外，for 循环中的“if”也有点问题。它声明一个本地引用，将其初始化为递归调用的结果。整个表达式是对 optional 的引用，如果 optional 有一个值，它有一个到 bool 的隐式转换。这是一个值得指出的有用习语，但更明确地说，这是等价的：

    if (auto const & aWay = howSum(targetSum-num, numbers, memo); aWay.has_value())

这是一个充实的例子，有几个测试用例来证明它是有效的。 https://godbolt.org/z/cWrdhvM1n

Answer 2

我也被这个问题困住了。这就是我让它工作的方式。

// howSum function
vector<int> howSum(int target, vector<int> numbers, unordered_map<int, vector<int>> &dp ){

    // base case 1 - for dp
    if(dp.find(target)!=dp.end()) return dp[target];

    // making a vector to return in the following base cases
    vector<int> res;

    // base case 2
    if(target == 0) {
        return res;
    }

    // base case 3
    if(target<0) {
        res.push_back(-1); // using -1 instead of NULL
        return res;
    }

    // the actual logic for the question
    for(int i=0;i<numbers.size();i++){
        int remainder = target - numbers[i];
        vector<int> result = howSum(remainder,numbers,dp); // recursion

        // if result vector doesn't contain -1, push target to result vector
        if(find(result.begin(),result.end(),-1)==result.end()){
            result.push_back(numbers[i]);
            dp.emplace(target,result);
            return result;
        }
    }
    res.push_back(-1);
    dp.emplace(target,res);
    return res;
}

// main function
int main(){

    vector<int>numbers = {20,50};
    unordered_map<int, vector<int>> dp;
    vector<int> res = howSum(300,numbers,dp);

    for(int i=0;i<res.size();i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

将 JavaScript 函数转换为 C++

Converting JavaScript function to C++

javascript

c++

dynamic-programming