O(1) 的小樂

/*
ID: lvxiaol3
LANG: C++
TASK: money
*/
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <cstdio>
using namespace std;

int main()
{
    ifstream fin("money.in");
    ofstream fout("money.out");
    int V, N;
    fin>>V>>N;
    vector<int> Coin(V);
    for(int i=0; i<V; i++) fin>>Coin[i];
    sort(Coin.begin(),Coin.end());

    long long  dp[2][10005];
    for(int i=0;i<V; i++) dp[i%2][0]=1LL;
    int temp=Coin[0];
    while(temp<=N) {dp[0][temp]=1;temp+=Coin[0];}

    for(int i=1; i<V;i++)
    {
        for(int j=1;j<=N;j++)
        {
            int m=j;
            dp[i%2][j]=0;
            while(m>=0)
            {
                dp[i%2][j]+=dp[(i-1)%2][m];
                m-=Coin[i];
            }
        }
    }
    fout<<dp[(V-1)%2][N]<<endl;

    return 0;
}
/*
3 10
1 2 5

1 1 1 1 1 1 1 1 1 1 1
1 1 2 2 3 3 4 4 5 5 6
1 1 2 2 3 4 5 6 7 8 10
10

Process returned 0 (0x0)   execution time : 0.027 s
Press any key to continue.

*/
// dp[k][n] the previous k kind of coins consist of n
// dp[k][n]= /sum{dp[k-1][n-p*v[k]] } p>=0

下面這一步的dp優(yōu)化贊！利用DP狀態(tài)改變的順序來優(yōu)化dp的復(fù)雜度
/*
for(i=0; i<v; i++) {
        fscanf(fin, "%d", &c);

        for(j=c; j<=n; j++)
            nway[j] += nway[j-c];
    }
*/