目录

1. 问题描述

2. 解题分析

 2.1 初始算法流程

2.2 优化

3. 代码及测试

4. 后记

1. 问题描述

讯享网

2. 解题分析

        这个题目第一感就是动态规划。

        对于（m, n）形状（如下图所示，m代表横向的长度，n代表纵向的高度）。为了方便起见，参照以下图右上角这样的坐标说明。

        每切一刀并吃掉小的那一块后留下的仍然是一个长方形。

        但是由于需要确保从头到尾两个人分到的蛋糕一样多，所以子问题并不单纯由长方形的尺寸决定。还要考虑进去当前轮到谁切，以及两个各自已经分到的蛋糕大小。

 2.1 初始算法流程

        考虑“递归+Memoization”的实现方式，得到算法流程如下所示。

        初始状态为who=0, eat=[0,0]，因此调用search(M,N,0,0,0)即可。 

2.2 优化

        进一步考虑优化。

【优化1】

        由于总是吃掉较小的那一块。

        因此，比如说纵向切的时候，x=1与x=(m-1)其实是等价的。横向切的情况也同理。这样切分的次数可以大约减小一半。

【优化2】

        最终只关心两者分到的是不是相同，并不需要关心各自分到的绝对量（当然在本题中两者平分的话所分的量也是确定的），因此可以用一个变量diff来去掉eat[2]。在跟踪统计diff时，第1个人的份加进去，第2个人的份则减掉，即可。

        进一步，考虑每一步分掉的量为z，每一步用(diff = z – diff)的方式跟踪的话，连who(表示当前轮到谁切分)都可以省掉了。这是原题解给出的技巧，确实小巧精致！

【优化3】

        由于对称性，(m,n)与(n,m)两种形状其实也是等价的，由此可以进一步减少需要计算的子问题个数。比如说M=8,N=4与M=4,N=8其实是相同的，只不过一个是横着放，另一个是直着放。因此可以籍此减少一半的搜索。体现为以下这条语句：

m, n = (n,m) if n>m else (m,n)

        考虑以上优化策略后，得到以下代码。

3. 代码及测试

讯享网# -*- coding: utf-8 -*- """ Created on Thu Oct 14 07:49:38 2021 @author: chenxy """ # import sys import time # import datetime # import math # import random from typing import List # from queue import Queue # from collections import deque import itertools as it import numpy as np memo = dict() BIGINT = 10000 def cut_cake2(m:int,n:int,diff:int)->int: ''' Parameters ---------- m : int Horizontal width of the cake. n : int Vertical height of the cake. diff : int Record the difference of eat quantity between two peoples. Returns ------- int The minimal cut length, starting from the current state. ''' global memo # print('cut_cake:', m,n,who) m, n = (n,m) if n>m else (m,n) if (m,n,diff) in memo: return memo[(m,n,diff)] if m==1 and n==1: # Reach the goal. if diff == 1: return 0 else: memo[(m,n,diff)] = BIGINT return BIGINT mincuts = BIGINT # Vertical trial Cut for x in range(1,m//2+1): new_m = m-x # Keep the larger part new_n = n eat_smaller = n * x cutlen = n + cut_cake2(new_m,new_n,eat_smaller - diff) if mincuts > cutlen: mincuts = cutlen # Horizontal trial cut for y in range(1,n//2+1): new_m = m new_n = n-y # Keep the larger part eat_smaller = m * y cutlen = m + cut_cake2(new_m,new_n,eat_smaller - diff) if mincuts > cutlen: mincuts = cutlen memo[(m,n,diff)] = mincuts return mincuts M = 16 N = 12 tStart = time.perf_counter() mincuts = cut_cake2(M,N,0) tCost = time.perf_counter() - tStart print('M={0}, N={1}, mincuts={2}, tCost = {3:6.3f}(sec)'.format(M,N,mincuts,tCost))

        运行结果：

                M=16, N=12, mincuts=47, tCost =  0.036(sec)

                M=30, N=30, mincuts=107, tCost =  1.751(sec)

4. 后记

        程序运行的速度倒是足够快了，但是熟悉的尴尬又重现了。原书给的答案是46，以上结果是47。有些结果一看就是十万八千里的离谱，那就知道肯定根本的机制有问题，这种问题通常反而容易解决。本题这样差1。。。这是一个根本性的问题呢，还是一个小的纰漏呢？很难判断。这种问题可能反而很难解决。

        之所以总是敢厚着脸皮把不完全正确的题解贴出来，是因为我认为从纠错中学习是一种重要的学习路径。即便是出题者也不一定是每道题一上来就是漂亮的正解，可能也需要经过纠错、优化的迭代才能得到最终呈现在读者面前的漂亮的正解（书籍出版由于容量的约束不可能把所有的过程都呈现出来）。

        老问题：谁能帮我指出错在哪儿呢？

        [2021-10-17] 搞笑搞大了。。。（原书给的）答案确实是47。我不知道是出了什么错觉（汗。。。）竟然把47看成46，主动判自己错了。。。昏头了^-^
     

        上一篇：程序员的算法趣题Q54: 偷懒的算盘

        下一篇：Q56: 鬼脚图中的横线

        本系列总目录参见：程序员的算法趣题：详细分析和Python全解