同样几块长度不同的地板,放进材料箱和从左到右铺成小路,会产生两种计数。前者只关心各长度用了多少块,后者还关心排列顺序。没有先定义答案身份,方案数就容易算错。
先固定规则和输入
选定三种互不相同的正整数长度,每种可无限使用,目标是恰好拼成指定总长。组合按各类使用数量区分;排列按从左到右的长度序列区分。空长度只有一种空方案,负长度没有方案。
三种长度[2, 4, 6],目标总长16
把结果按步骤记下来
总长0:按使用数量区分有1种,按左右顺序区分有1种。空方案作为递推起点。
总长1:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长2:按使用数量区分有1种,按左右顺序区分有1种。后者由每种可用末块对应的较短序列累加。
总长3:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长4:按使用数量区分有2种,按左右顺序区分有2种。后者由每种可用末块对应的较短序列累加。
总长5:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长6:按使用数量区分有3种,按左右顺序区分有4种。后者由每种可用末块对应的较短序列累加。
总长7:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长8:按使用数量区分有4种,按左右顺序区分有7种。后者由每种可用末块对应的较短序列累加。
总长9:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长10:按使用数量区分有5种,按左右顺序区分有13种。后者由每种可用末块对应的较短序列累加。
总长11:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长12:按使用数量区分有7种,按左右顺序区分有24种。后者由每种可用末块对应的较短序列累加。
总长13:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长14:按使用数量区分有8种,按左右顺序区分有44种。后者由每种可用末块对应的较短序列累加。
总长15:按使用数量区分有0种,按左右顺序区分有0种。后者由每种可用末块对应的较短序列累加。
总长16:按使用数量区分有10种,按左右顺序区分有81种。后者由每种可用末块对应的较短序列累加。
目标长度的组合数10,有序序列数81。一组可行的三类数量为[0, 1, 2];若为空则表示恰好拼成目标的方案不存在。
自己复核的办法
组合可枚举三类数量并检查总长,排列则把最后一块拆出来求和。重复长度不可当成不同种类,同一长度的实体副本也没有额外身份。这样才能避免把材料选择误算成排列。
建议先遮住结果,用本例原始输入独立完成一遍,再逐项对照。若出现差异,先找最早不一致的位置,检查索引从零还是从一开始、边界是否包含,以及比较或更新发生的先后。只比较最后一个数,往往无法分辨规则理解与计算步骤分别出了什么问题。
使用这个练习的边界
规则只统计一维精确长度,没有接缝损耗、方向、颜色或数量上限。如果关卡实际有库存限制,就不能继续使用无限供给的递推;先改约束再计算,结果才有可比性。
