# getting wrong answer on spoj PHIDIAS problem using dp.

I have used 3D dp in this case i.e dp[i][j][k] where dp[i][j][k] means i have to maximize utilization of (i X j) rectangle with k options and i have given the answer as w*h - dp[w][h][n].

``````lp(i,1,wd+1){
lp(j,1,ht+1){
lp(k,1,n+1){
dp[i][j][k] = dp[i][j][k-1];
if(i>=w[k] && j>=h[k]){
dp[i][j][k] = max(dp[i][j][k],dp[i-w[k]][j][k] + dp[w[k]][j-h[k]][k] + w[k]*h[k]);
dp[i][j][k] = max(dp[i][j][k],dp[i][j-h[k]][k] + dp[i-w[k]][h[k]][k] + w[k]*h[k]);
}
}
}
}
``````

ya i know 2d solution, but what is wrong with this 3d. I have checked various test cases and it is giving correct answer same answer as given by your 2d solution, but what is wrong in this case. or if you can find the test case in which it gives wrong solution.

Solved it using top down…U can do it using 2d dp…

``````int phidias(int w, int h) {
if(dp[w][h] > -1) return dp[w][h];
int &res = dp[w][h] = w * h, tmp;
for(int i = 1; i <= (w >> 1); i++) {
tmp = phidias(i, h);
if(tmp < res) tmp += phidias(w - i, h);
if(tmp < res) res = tmp;
}
for(int i = 1; i <= (h >> 1); i++) {
tmp = phidias(w, i);
if(tmp < res) tmp += phidias(w, h - i);
if(tmp < res) res = tmp;
}
return res;
``````

}

``````cin>>W>>H>>n;
memset(dp, -1, sizeof dp);
for(i = 0; i < n; i++) {
scanf("%d %d", &w[i], &h[i]);
dp[w[i]][h[i]] = 0;
}
phidias(W, H));``````

Its neat and clean…hope u can easily understand it.

ya i know 2d solution, but what is wrong with this 3d. I have checked various test cases and it is giving correct answer same answer as given by your 2d solution, but what is wrong in this case. or if you can find the test case in which it gives wrong solution.