xyDnz 发布于一月 15, 2021 分享 发布于一月 15, 2021 (已修改) 稍微想了一下，这道题的本质是要讲一个阶梯形的图形分割成两部分，并且这两部分在远正方形的分割上也是两块联通的分割子集，将原图形中的交点作为坐标，右上角为（0,0），左下角为（n，n），分为三种情况，分割线连右边和下边，分割线连接右边和斜边，分割线连接斜边和下边，第二种情况可以看做是分割线从（0,0）出发到垂直向下后再到斜边上，第二种情况本质上会将中间分成3分所以排除，第三种情况和第一种情况实际上是对称所以最后只要答案乘以2再去掉对称相等的特例，这样这题就变成从（0,0）出发不能经过底边的到（x，x）(1<=x<=n)的合法路线合计有多的爆搜题 大体思路应该是这样，实际上可能还有一些细节需要优化，不过最近一年备战考研算法荒废了半年，就不丢人了，摸了 一月 15, 2021，由xyDnz修改 链接到点评
推荐贴