4e494b's blog

By 4e494b, history, 5 weeks ago, In English,

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][1] = 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[610][610];
int H[250];
int W[250];
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;
    }
}

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • 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[0][] and dp[][0] 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
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you for your help feodorv. Your explanation made everything clear. Top down approach took 0.86s and bottom up approach takes 0.26s.