1359.有效的快递序列数目

链接：1359.有效的快递序列数目
难度：Hard
标签：数学、动态规划、组合数学
简介：请你统计所有有效的 收件/配送 序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

题解 1 - typescript

• 编辑时间：2021-12-11
• 执行用时：76ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：动态规划，每次多一个快递，就计算新快递可能放置的数量。

const mod = 1e9 + 7;
function sum(n: number) {
  return ((1 + n) * n) / 2;
}
function countOrders(n: number): number {
  const dp = new Array(n).fill(0);
  dp[0] = 1;
  for (let i = 1; i < n; i++) {
    const num = 1 + 2 * i;
    dp[i] = (dp[i - 1] * sum(num)) % mod;
  }
  return dp[n - 1];
}

题解 2 - typescript

• 编辑时间：2021-12-11
• 执行用时：76ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：优化上一题解。

const mod = 1e9 + 7;
function sum(n: number) {
  return ((1 + n) * n) / 2;
}
function countOrders(n: number): number {
  let ans = 1;
  for (let i = 2; i <= n; i++) ans = (ans * sum(1 + 2 * (i - 1))) % mod;
  return ans;
}