1359. Pickup Deliveries

Count All Valid Pickup and Delivery Options

又是一道非常适合Bottom Up的动态规划题

比552号题更简单些 起码我是这么觉得

Base Case

当只有一个订单时 只有一种方案

先取(P)后送(D) 组合数便是1

长得这样子：$(P_1, D_1)$

观察往上爬的路线🧗

1. $P_2$和$D_2$如何配置

$P_i$永远要在$D_i$的左边 这是题目的要求

因此我们先来留意$P_2$该摆哪儿

$(P_1, D_1)$这样的组合 有三个槽位(Slots)可安插$P_2$

放进$P_2$后 自然形成四个槽位 但这四个槽位

就$P_2$的视角来说 是有变化滴

I. 放在$P_1$左：1 + 3 的格式

$+$号左 是指 $P_2$左边 的槽位数

$+$号右 是指 $P_2$右边 的槽位数

II. 放在$P_1$和$D_1$中：2 + 2 的格式

III. 放在$D_1$右：3 + 1 的格式

刚才提到$P_i$永远要在$D_i$的左边

因此$P_2$确定位置后 $D_2$永远只能选

上述那些+号右边的槽位

总共有$1 + 2 + 3 = 6$种可选

于是两份订单数量时 组合数便是$1 \times 6 = 6$

2. 由此想像一下$P_j$和$D_j$ 若$2 \leq j$

$P_j$和$D_j$即将入队时 前面肯定有$j - 1$份订单

形成了总长为$2j - 2$的序列

$P_j$的插入位置于是有$2j - 1$个槽位

这些槽位由左到右 给予$D_j$的合法槽位数

依序是$2j - 1, ..., 1$个这么多

这不就是等差级数和$(2j - 1)j$嘛

恰好是在$P_j$和$D_j$的安排上

会让截至上一轮的组合数$C_{j - 1}$ 放大的倍率

于是我们的状态转移方程有的是

$C_j = C_{j - 1} \times j(2j - 1) \; \forall \; j \in N; 2 \leq j$

好啦～～可直接进入手刻代码环节啰🧑🏻‍💻👩🏻‍💻

老话一句 数字可能来到天文级 记得要取模哦

C++

#include <cmath>
using namespace std;

int countValidSequences(int totalOrders) // LeetCode Q.1359.
{
    long long modulo = pow(10, 9) + 7; // Long long prevents overflow.

    // Base case when n is 1: pickup 1 followed by delivery 1.
    long long validSequences = 1;

    for (int prevOrderNum = 1; prevOrderNum <= totalOrders - 1; prevOrderNum++) {
        int spotsCount = 2 * prevOrderNum + 1;

        // Sum from 1 to spots count.
        int multiple = spotsCount * (spotsCount + 1) / 2;

        validSequences *= multiple;
        validSequences %= modulo;
    }

    return validSequences;
}

Python

def count_valid_sequences(total_orders: int) -> int:  # LeetCode Q.1359.
    modulo = 10 ** 9 + 7

    # Base case when n is 1: pickup 1 followed by delivery 1.
    valid_sequences = 1

    for prev_order_num in range(1, total_orders):
        spots_count = 2 * prev_order_num + 1

        # Sum from 1 to spots count.
        multiple = spots_count * (spots_count + 1) // 2

        valid_sequences *= multiple
        valid_sequences %= modulo

    return valid_sequences

时间$O(n)$ 空间$O(1)$ 状态转移方程也要练习手写呀