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;
}
}
