[Math] Dynamic programming– chocolate bar

dynamic programming

There is a chocolate bar that has $m\times n$ rectangles. In each step, we can break one piece to two ones along a line. Give a dynamic programming algorithm which computes the minimal number of breaks to “squareize” a $1 \times 1$ bar. Can someone help?

Best Answer

The number of steps in any process is always $mn-1$ since the number of pieces increases by $1$ after each cut, and you want to reach a state with $mn$ pieces.

Here is a possible way to solve the problem with dynamic programming. Set up a bidimensional array M[][] such that M[x][y] is the minimum number of steps to squarisize the grid. It is then clear tht M[x][y] is equal to $\min(\min( M[k][y]+M[x-k][y]+1),\min(M[x][k]+M[x][y-k]+1))$, where $k$ ranges over all apropriate values.

Using this we can calculate M[][] recursively as is shown in thefollowing code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=100;
const int INF=1e9;
int M[MAX][MAX];

void actualize(int x, int y){
    int minimum=INF;
    for(int k=1;k<x;k++){
        minimum=min(minimum,M[k][y]+M[x-k][y]+1);
    }
    for(int k=1;k<y;k++){
        minimum=min(minimum,M[x][k]+M[x][y-k]+1);
    }
    M[x][y]=minimum;
}

int main(){
    for(int i=1;i<MAX;i++){
        for(int j=1;j<MAX;j++){
            if(i==1 && j==1) continue;
            actualize(i,j);
        }
    }
    int m,n;
    cin >> m >> n;
    cout << M[m][n] << endl;
}

You can optimize this code by making an auxiliary table calculating partial minimums, but of course this is irrelevant, since the actual optimal solution is to just print $mn-1$

Related Question