首页 > 其他 > 详细

HackerRank - "The Coin Change Problem"

时间:2015-06-30 06:33:39      阅读:463      评论:0      收藏:0      [点我收藏+]

If coin order matters, that is, each sequence is unique, the DP function is simple enough to make it 1D DP. But key is that order DOESN‘T matter, so we need to add one more state: ending coin. And for each DP advance step, we only put >= coins.

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

typedef unsigned long long ULL;

int main()
{
    unsigned n, m;
    cin >> n >> m;
    vector<ULL> v(m);
    for (unsigned i = 0; i < m; i++)
        cin >> v[i];
    std::sort(v.begin(), v.end());

    //    dp[val][ending coin]
    vector<vector<ULL>> dp(n + 1, vector<ULL>(m, 0));
    dp[0][0] = 1;
    for (unsigned i = 0; i <= n; i++)
    for (unsigned j = 0; j < m; j ++)
    {
        for (unsigned k = j; k < m; k ++)
        {    
            if((ULL(i) + v[k]) <= ULL(n))
                dp[ULL(i) + v[k]][k] += dp[i][j];
        }
    }
    ULL ret = 0;
    for(unsigned i = 0; i < m; i ++)    ret += dp[n][i];
    cout << ret << endl;
    return 0;
}

HackerRank - "The Coin Change Problem"

原文:http://www.cnblogs.com/tonix/p/4609312.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!