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?
Think of the dp as being of the form
dp[n][h]
wheren
is the index of the day andh
is the happiness that can be bought. Now the transition isdp[i][j] = min(dp[i - 1][j - h[i]] + c[i], dp[i][j])
. However, you can notice that for calculatingdp[i]
we only need values fromdp[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.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