使用递归函数计算钢条裁切为指定规格短棒的合法方案数

问题核心逻辑 #

首先明确合法方案的判定规则：

• 所有裁切出来的短棒只能是[5,8,17,28]四种长度
• 最终剩余废料 = 原长度 - 所有裁切短棒长度之和 ≤3
• 方案不区分裁切顺序（如先切5再切8和先切8再切5算同一方案，避免重复计数）

递归实现思路 #

为了避免重复计数，递归时限制每次选择的短棒长度不小于上一次选择的长度，从根源上消除顺序不同导致的重复统计：

1. 递归函数传入两个参数：剩余待裁切长度remain、当前允许选择的最小短棒索引start
2. 终止条件：
   • 若remain ≤3：符合废料要求，返回1（代表找到1种合法方案）
   • 若remain <5：剩余长度不够切最小的短棒且废料超过3，返回0
3. 递归逻辑：从start下标开始遍历所有短棒，只要短棒长度≤剩余长度，就累加递归调用的返回值（剩余长度减去当前短棒长度，start保持当前下标，允许后续继续选相同长度的短棒）

完整可运行代码 #

def cut(n):
    rods = [5, 8, 17, 28]
    def dfs(remain, start):
        # 剩余长度<=3，符合废料要求，计数+1
        if remain <= 3:
            return 1
        # 剩余长度不够切最小的短棒且废料超3，无效方案
        if remain < 5:
            return 0
        total = 0
        # 从start开始选，避免重复计数
        for i in range(start, len(rods)):
            if rods[i] <= remain:
                total += dfs(remain - rods[i], i)
        return total
    return dfs(n, 0)

if __name__ == "__main__":
    count = int(input())
    for _ in range(count):
        n = int(input())
        print(cut(n))

代码验证 #

输入提供的示例输入：

3
100
160
240

输出结果和示例完全一致：

71
229
667

内容的提问来源于stack exchange，提问作者Freedom