Count All Valid Pickup and Delivery Options Solutions in C++

/// Source : https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
/// Author : liuyubobobo
/// Time   : 2020-02-23

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n * n)
/// Space Complxity: O(n * n)
class Solution {

private:
    long long MOD = 1e9 + 7;

public:
    int countOrders(int n) {

        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
        return dfs(0, 0, n, dp);
    }

private:
    int dfs(int open, int close, int n, vector<vector<int>>& dp){

        if(open == n && close == n) return 1;
        if(dp[open][close] != -1) return dp[open][close];

        int res = 0;
        if(open < n) res += (long long)(n - open) * (long long)dfs(open + 1, close, n, dp) % MOD;
        if(close < open) res += (long long)(open - close) * (long long)dfs(open, close + 1, n, dp) % MOD;
        return dp[open][close] = res % MOD;
    }
};


int main() {

    cout << Solution().countOrders(1) << endl;
    // 1

    cout << Solution().countOrders(2) << endl;
    // 6

    return 0;
}

/// Source : https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
/// Author : liuyubobobo
/// Time   : 2020-02-23

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n * n)
/// Space Complxity: O(n * n)
class Solution {

private:
    long long MOD = 1e9 + 7;

public:
    int countOrders(int n) {

        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        dp[1][0] = dp[1][1] = n;
        for(int i = 2; i <= n; i ++)
            dp[i][0] = (long long)dp[i - 1][0] * (long long)(n - i + 1) % MOD;

        for(int i = 2; i <= n; i ++)
            for(int j = 1; j <= i; j ++){
                dp[i][j] = 0;
                dp[i][j] += (long long)(n - i + 1) * (long long)dp[i - 1][j] % MOD;
                dp[i][j] += (long long)(i - j + 1) * (long long)dp[i][j - 1] % MOD;
            }
        return dp[n][n];
    }
};


int main() {

    cout << Solution().countOrders(1) << endl;
    // 1

    cout << Solution().countOrders(2) << endl;
    // 6

    return 0;
}

/// Source : https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
/// Author : liuyubobobo
/// Time   : 2020-02-23

#include <iostream>
#include <vector>

using namespace std;


/// Mathematics
/// Time Complexity: O(n)
/// Space Complxity: O(1)
class Solution {

private:
    long long MOD = 1e9 + 7;

public:
    int countOrders(int n) {

        int res = 1;
        for(int i = 0; i + 1 < n; i ++)
            res = (long long)res * (long long)(n - i) * (long long)(2 * (n - i) - 1) % MOD;
        return res;
    }
};


int main() {

    cout << Solution().countOrders(1) << endl;
    // 1

    cout << Solution().countOrders(2) << endl;
    // 6

    return 0;
}