a bit of dp: SPOJ - NOCHANGE

Problem Statement:
SPOJ - NOCHANGE

Summary:
Can we choose \(c_1, c_2, \ldots, c_k\) such that \(c_1v_1 + c_2v_2 + \ldots + c_kv_k = X\) where \(c_1 \geq c_2 \geq \ldots \geq c_k\)?
\(k \leq 5\), \(X\leq 10^5\)

Solution:
Another interesting DP technique. Let \(S_k\) be a set such that if \(n \in S_k\), then \(n\) can be represented as a sum of \(v_i\) with non-increasing coefficients \(c_i\) as above. (Notice that \(0 \in S_k\) )Now consider \(S_{k+1}\). For each \(n\) in \(0, \ldots, X\), \(n \in \S_{k+1}\) if and only if there is \(m \in S_k\) such that \(n = m + c(v_1 + v_2 + \ldots + v_{k+1})\) for some \(c\) (Hence the resulting coefficients will be non-decreasing as well).
Implementation:

bool solve(){
    sum[0] = v[0];
    for(int i=1;i<K;++i){
        sum[i] = sum[i-1] + v[i];
    }
    for(int i=0;i<=N;++i){
        dp[i] = 0;
    }
    dp[0] = 1;
    for(int i=0;i<=N;++i){
        if(dp[i]) dp[i+v[0]] = 1;
    }
    for(int k=1;k<K;++k){
        for(int i=0;i<=N;++i){
            if(!dp[i]) continue;
            int u = i + sum[k];
            if(u>N) break;
            dp[u] = 1;
        }
    }
    return dp[N];
}