4e494b's blog

By 4e494b, history, 3 months ago, , Hello codeforces community, I need your help again.

I was solving this problem on SPOJ. I did it using top-down approach and when I tried to convert it to bottom-up, I just could not think of base cases. So I googled for the bottom up solution of this problem. I was taken to this Topcoder Link. I tried to understand the logic behind dp = 1, but I just could not wrap my head around it.

It would be really helpful, if you could explain me your own technique (bottom-up ofc) to solve this problem or explain the reasoning behind the dp state in topcoder article.

Here is my top-down code

#include<bits/stdc++.h>

using namespace std;

int dp;
int H;
int W;
int n;

int sol(int w, int h){
int res = w*h;
if(dp[w][h] != -1){
return dp[w][h];
}
for(int i=0; i<n; i++){
if(w - W[i] >= 0 && h - H[i] >= 0){
res = min(res, sol(w-W[i],h)+sol(W[i],h-H[i]));
res = min(res, sol(w,h-H[i])+sol(w-W[i],H[i]));
}
}
dp[w][h] = res;
return dp[w][h];
}

int main()
{
int t;
cin >> t;
while(t--){
int w,h;
cin >> w >> h;
cin >> n;
for(int i=0; i<n; i++){
cin >> W[i] >> H[i];
}
memset(dp, -1, sizeof(dp));
cout << sol(w,h) << endl;
}
}  Comments (2)
 » For bottom-up DP you should traverse consequently all DP states: for( ww = 1; ww <= W; ++ww) for( hh = 1; hh <= H; ++hh) Base DP states here are dp[] and dp[] with zero values (no need to initialize its specially because of global variables). Finish state is dp[W][H]. dp[][] has the same meaning as for top-down DP. Code#include #define MAXN 200 #define MAXS 600 int W, H, N, w[MAXN], h[MAXN]; int dp[MAXS+1][MAXS+1]; int solution( void ) { int ww, hh; for( ww = 1; ww <= W; ++ww) for( hh = 1; hh <= H; ++hh) { int res = ww * hh, i; for( i = 0; i < N; ++i) if( w[i] <= ww && h[i] <= hh ) { int v = dp[ww-w[i]][hh] + dp[w[i]][hh-h[i]]; if( v < res ) res = v; v = dp[ww][hh-h[i]] + dp[ww-w[i]][h[i]]; if( v < res ) res = v; } dp[ww][hh] = res; } return dp[W][H]; } int main( void ) { int t = 0; scanf( "%d", &t); while( t-- > 0 ) { int i; scanf( "%d %d %d", &W, &H, &N); for( i = 0; i < N; ++i) scanf( "%d %d", &w[i], &h[i]); printf( "%d\n", solution()); } return 0; }
•  » » 3 months ago, # ^ | ← Rev. 2 →   Thank you for your help feodorv. Your explanation made everything clear. Top down approach took 0.86s and bottom up approach takes 0.26s.