thequacker's blog

Help required in DP problem
By thequacker, history, 4 months ago, In English

Problem Link

void solve(){
    int n,x;
    cin>>n>>x;
    vector<int>c(n),h(n);
    for(int i=0;i<n;i++){
        cin>>c[i]>>h[i];
    }

    int max_h=accumulate(h.begin(),h.end(),0ll);
    vector<int>dp(max_h+1,1e9);

    dp[0]=0;
    // 0 i i i i i i 
    for(int i=0;i<n;i++){
        for(int j=max_h;j>=0;j--){
            if(j-h[i]>=0 && dp[j-h[i]]+c[i]<=i*x){
                dp[j]=min(dp[j-h[i]]+c[i],dp[j]);
            }
        }
    }
    for(int i=max_h;i>=0;i--){
        if(dp[i]<=(n-1)*x){
            cout<<i<<endl;
            break;
        }
    }
}

why is the loop being runned from max_h to 0 and not 0 to max_h?
because we clearly need dp[j-h[i]] to compute dp[j]
if possible can someone explain this problem in depth?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Think of the dp as being of the form dp[n][h] where n is the index of the day and h is the happiness that can be bought. Now the transition is dp[i][j] = min(dp[i - 1][j - h[i]] + c[i], dp[i][j]). However, you can notice that for calculating dp[i] we only need values from dp[i - 1] and hence to save space we can do updates in-place and since $$$ j - h[i] \lt j$$$ we can loop backwards and update in the same array.

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

because there might be multiple wrong updates while iterating 0 to max

eg you update dp[i] with dp[i-1] then again you update dp[i+1] with the updated dp[i] instead of the orignal one, so either keep another dummy array for updates and swap dummy with dp OR make a 2D dp

→ Reply