I googled the problem and found the solution, but I was not able to understand the recurrence relation.Any help will be appreciated.

If we’re not able to cut a slab with height H and width W is H*W.

Suppose we have a slab of size H*W.

```
+-------------------+
| |
| | H
| |
+-------------------+
W
```

If we cut a plate of size y*x,

```
x
+-------------------+
| y |_ _ _ _|
| | H
| |
+-------------------+
W
```

then the waste is the minimum of splitting the slab into 2 of sizes H * (W-x) and (H-y) * x

```
x
+-------------------+
| y |_ _ _ _|
| | | H
| | |
+-------------------+
W
```

or splitting into y * (W-x) and (H-y)*W

```
x
+-------------------+
| _ _ _ _ y |_ _ _ _|
| | H
| |
+-------------------+
W
```

We can see that the slab splits are always made into smaller pieces, so a bottom-up dynamic programming algorithm can reuse the minimum cost of splitting smaller slabs.

3 Likes

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]);
}
}
}
}
```

i am getting wrong answer.

please see it.