algorithm - 动态规划 - 达到给定目标的组合数量

Question

这是一个基本的动态规划问题 - 分数组合的数量。我知道这个问题的自下而上方法效果很好。

但是，我无法为该问题找到一种自上而下的解决方案。缓存递归部分为我们提供了更多必要的组合（其中分数的排序/序列也是一个因素，因此，为了避免它，我们需要提供一个约束以使序列单调增加。这是相同的递归方法。动态编程- 达到给定分数的不同组合的数量

这是我当前的代码：

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

int helper(int target, vector<int>& coins, vector<int>& cache, int min) {
    if(target < 0) return 0;
    if(target == 0) return 1;
    if(cache[target] != 0) return cache[target];

    for(auto& c : coins) {
        if(target >= c && min <= c) {
            //cout << min << " " << c << " " << target << endl;
            cache[target] += helper(target-c, coins, cache, c) ;
            //cout << cache[target] << endl;            
        }

    }

    return cache[target];

}


int main() {

    vector<int> coins{2, 3};

    int target = 7;
    vector<int> cache(target+1, 0);
    cache[0] = 1;
    cache [7] = helper(target, coins, cache, 1);

    for (auto& x : cache) cout << x << endl;
    return 0;
}

这是可运行的ideone链接。

标签： algorithmdynamic-programming