完全分割一块巧克力需要多少次休息时间？

Question

CodeWars 再次挑战。今天我遇到了这个问题：

“您的任务是将给定尺寸 nxm 的巧克力棒分成小方块。每个方块的大小为 1x1 且牢不可破。实现一个函数，该函数将返回所需的最少中断次数。

例如，如果给您一块 2 x 1 大小的巧克力棒，您可以在一次中断时将其拆分为单个方块，但对于 3 x 1 大小，您必须进行两次中断。

如果输入数据无效，您应该返回 0（因为如果我们没有任何可拆分的巧克力，则不需要中断）。输入将始终是一个非负整数。”

出于某种原因，无论我提供巧克力棒的哪一面，输出始终为 0。

我已经尝试过的：

object breakChocolate {

    var result = 0

    def breakChocolate(n: Int, m: Int) = {

        var t = n*m
        var i =0
        def breaking(y:Int): Unit ={
            if (t ==0 || t ==1)
                result = i
            else {
                breaking(t%2)
                i +=1
            }
        }
        result
    }
}

以下是测试：

测试结果：TestCases breakChocolate(5, 5) 应该返回 24 Test Failed

0 不等于 24 堆栈跟踪在 38 毫秒内完成 breakChocolate(7, 4) 应返回 27 测试失败

0 不等于 27 Stack Trace 在 1ms 内完成 76ms 内完成

Answer 1

要解决这个问题，您根本不需要递归。考虑巧克力盘的特殊情况：(1 xn)。要完全分割这个盘子，你需要 (n-1) 次中断。现在你有盘子 mx n。要将其分成 m 个形式 (1 xn)，您需要 (m-1) 个中断。所以休息的总数是

(m-1) + m*(n-1) ~ 
m - 1 + m*n - m ~ 
m*n - 1