4e494b's blog

By 4e494b, history, 5 years 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

| Write comment?