If we use F(m,n) to represent the minimum times

It is obvious that we can get the following equations:
1) F(m,n) = F(n,m)
2) F(1,1) = 0
3) For any m>0, F(m,1) = m-1
4) For any n>0, F(1,n) = n-1

For a m*n cells, we have (m-1) + (n-1) for the first split choice:
1) We can split from the ith (1<=i<=m-1) row, then:
    F(m,n) = F(i,n) + F(m-i,n) + 1
2) Or we can split from the jth (1<=j<=n-1) column, then:
    F(m,n) = F(m,j) + F(m,n-j) + 1

Then our algorithm is to select the minimum value from the (m-1)
+ (n-1) choices, the algorithm can be done in a recursive pattern.

We can have the following optimizations:
1) 1<=i<=[m/2]
2) 1<=j<=[n/2]

I believe the minimum times should be m*n-1.

#include <stdio.h>

#define INFINITY 999999

int chocalate(int m, int n)
{
  int i,j,count;

  if (m==1) return n-1;
  if (n==1) return m-1;

  int times = INFINITY;

  for (i=1; i<m/2+1; i++) {
    count =  chocalate(m-i,n) + chocalate(i,n) + 1;
    if (count < times) times = count;
  }
  for (j=1; j<n/2+1; j++) {
    count = chocalate(m,j) + chocalate(m,n-j) + 1;
    if (count < times) times = count;
  }

  return times;
}

int main()
{
  printf("The minimum times to split a %d*%d chocalte is %d\n", 10, 10, chocalate(10,10));
  return 0;
}

不过貌似算法效率极低啊，有什么意见改进没？

空间换时间，把已经计算过的存储起来，效率可以提高很多：

#include <stdio.h>

#define INFINITY 999999

#define MAXINDEX 1000

int F[MAXINDEX][MAXINDEX];

int chocalate(int m, int n)
{
  int i,j,count;

  if (m==1) return n-1;
  if (n==1) return m-1;
  if (F[m-1][n-1] != INFINITY) return F[m-1][n-1];

  int times = INFINITY;

  for (i=1; i<m/2+1; i++) {
    count =  chocalate(m-i,n) + chocalate(i,n) + 1;
    if (count < times) times = count;
  }
  for (j=1; j<n/2+1; j++) {
    count = chocalate(m,j) + chocalate(m,n-j) + 1;
    if (count < times) times = count;
  }

  F[m-1][n-1] = times;

  return times;
}

int main()
{
  int i, j;
  for(i=0; i<MAXINDEX; i++)
    for(j=0; j<MAXINDEX; j++)
      F[i][j] = INFINITY;

  printf("The minimum times to split a %d*%d chocalte is %d\n", 200, 200, chocalate(200,200));
  return 0;
}

欢迎大家继续改进