统计有效取派件方案回溯算法时间复杂度计算错误原因排查

• 递归调用次数估算错误：原估算默认所有2N步操作的全排列都属于合法递归路径，但该问题强制要求每个订单的取货操作必须早于送货操作，合法递归路径的总数远小于(2N)!。实际合法路径总数为(2N)! / 2^N：所有2N步的全排列中，每个订单的取货、送货顺序有一半为非法（送货在前），N个订单共排除2^{N种非法组合，最终合法路径数为全排列数除以2}N。
• 单次递归开销估算错误：原估算认为每次递归都会遍历2N个元素，实际两次for循环的有效遍历次数远低于该值：第一个循环仅遍历未完成取货的订单，最大遍历次数为N；第二个循环仅遍历已取货但未完成送货的订单，最大遍历次数为当前待配送订单数，远低于N。

代入数值计算即可对应观测到的运行结果：

• n=6时，合法递归调用总次数为12! / 2^6 = 7484400，仅700余万次运算，C++完全可以在常规时限内完成，符合n=6正常运行的观测结果。
• n=7时，合法递归调用总次数为14! / 2^7 = 681080400，接近7亿次运算，已经超出常规OJ的时限阈值，因此触发TLE，和实际表现完全一致。

如果要提升算法效率，可选择两种方案：

1. 增加记忆化缓存：递归状态仅由已取货订单数、已送货订单数两个变量决定，可缓存该状态的计算结果，避免重复计算，时间复杂度可优化至O(N^2)。
2. 直接使用数学递推：该问题的合法方案数满足递推关系 dp[n] = dp[n-1] * (2n - 1) * n % MOD，边界条件为dp[1] = 1，可在O(N)时间复杂度内完成计算。

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