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

~~~~~