# LeetCode 解題日誌心得

## 前言
我是一位清大電機的學生，之前在網路上發現有人會分享自己解題的過程，並跟其他人討論，所以想說我也來弄一個，主要是當作紀錄自己的解題思維

[toc]

## 題目

### 1359. Count All Valid Pickup and Delivery Options (Hard)
[題目連結](https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/)

#### 解題思路
這一題乍看之下很讓人難以摸清頭緒，不過仔細思考後就會發現這是一個排列組合＋遞迴的問題。簡單來說就是固定前面n-1組，然後插入第n組P/D。

接下來觀察一下規律，第一組有1種可能，第二組可以選擇將P插入在最前面/中間/最後面，然後對應的D有3/2/1個位置可以放，所以是第一組的可能性乘上(3 + 2 + 1)

然後觀察一下第三組，P可以插入的位置有5種可能，對應到的D就是(5 + 4 + 3 + 2 + 1)種可能性。所以第n組就是(2n - 1 + 2n - 2 + ... + 1)

現在規律知道了，就來看一下題目限制。他說n最大是500，所以O(n)的For迴圈完全沒有問題，同時要避免輸出太大，每次運算完都取餘數。確認完成之後就開始動工！

#### 程式碼

class Solution {
public:
    unsigned long long int sol = 1;
    unsigned long long int multi = 1;
    int countOrders(int n) {
        // x_1 = 1
        // x_2 = x_1 * (1 + 2 + 3)
        // x_3 = x_2 * (1 + 2 + 3 + 4 + 5)
        for (int i = 1; i <= n; i++) {
            sol *= multi;
            sol = sol % 1000000007;
            multi += (4 * (i + 1) - 3);
            multi = multi % 1000000007;
            // cout << "i: " << i << " sol: " << sol << " multi: " << multi << endl;
        }
        return sol;
    }
};