Skip to content

Commit 8505ad4

Browse files
committed
1359 solved.
1 parent 691a6ff commit 8505ad4

File tree

5 files changed

+142
-1
lines changed

5 files changed

+142
-1
lines changed
Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.15)
2+
project(cpp_1359)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_1359 main3.cpp)
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/// Source : https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
2+
/// Author : liuyubobobo
3+
/// Time : 2020-02-23
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Memory Search
12+
/// Time Complexity: O(n * n)
13+
/// Space Complxity: O(n * n)
14+
class Solution {
15+
16+
private:
17+
long long MOD = 1e9 + 7;
18+
19+
public:
20+
int countOrders(int n) {
21+
22+
vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
23+
return dfs(0, 0, n, dp);
24+
}
25+
26+
private:
27+
int dfs(int open, int close, int n, vector<vector<int>>& dp){
28+
29+
if(open == n && close == n) return 1;
30+
if(dp[open][close] != -1) return dp[open][close];
31+
32+
int res = 0;
33+
if(open < n) res += (long long)(n - open) * (long long)dfs(open + 1, close, n, dp) % MOD;
34+
if(close < open) res += (long long)(open - close) * (long long)dfs(open, close + 1, n, dp) % MOD;
35+
return dp[open][close] = res % MOD;
36+
}
37+
};
38+
39+
40+
int main() {
41+
42+
cout << Solution().countOrders(1) << endl;
43+
// 1
44+
45+
cout << Solution().countOrders(2) << endl;
46+
// 6
47+
48+
return 0;
49+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
/// Source : https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
2+
/// Author : liuyubobobo
3+
/// Time : 2020-02-23
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Dynamic Programming
12+
/// Time Complexity: O(n * n)
13+
/// Space Complxity: O(n * n)
14+
class Solution {
15+
16+
private:
17+
long long MOD = 1e9 + 7;
18+
19+
public:
20+
int countOrders(int n) {
21+
22+
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
23+
dp[1][0] = dp[1][1] = n;
24+
for(int i = 2; i <= n; i ++)
25+
dp[i][0] = (long long)dp[i - 1][0] * (long long)(n - i + 1) % MOD;
26+
27+
for(int i = 2; i <= n; i ++)
28+
for(int j = 1; j <= i; j ++){
29+
dp[i][j] = 0;
30+
dp[i][j] += (long long)(n - i + 1) * (long long)dp[i - 1][j] % MOD;
31+
dp[i][j] += (long long)(i - j + 1) * (long long)dp[i][j - 1] % MOD;
32+
}
33+
return dp[n][n];
34+
}
35+
};
36+
37+
38+
int main() {
39+
40+
cout << Solution().countOrders(1) << endl;
41+
// 1
42+
43+
cout << Solution().countOrders(2) << endl;
44+
// 6
45+
46+
return 0;
47+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/// Source : https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
2+
/// Author : liuyubobobo
3+
/// Time : 2020-02-23
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Mathematics
12+
/// Time Complexity: O(n)
13+
/// Space Complxity: O(1)
14+
class Solution {
15+
16+
private:
17+
long long MOD = 1e9 + 7;
18+
19+
public:
20+
int countOrders(int n) {
21+
22+
int res = 1;
23+
for(int i = 0; i + 1 < n; i ++)
24+
res = (long long)res * (long long)(n - i) * (long long)(2 * (n - i) - 1) % MOD;
25+
return res;
26+
}
27+
};
28+
29+
30+
int main() {
31+
32+
cout << Solution().countOrders(1) << endl;
33+
// 1
34+
35+
cout << Solution().countOrders(2) << endl;
36+
// 6
37+
38+
return 0;
39+
}

readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -936,7 +936,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
936936
| 1356 | [Sort Integers by The Number of 1 Bits](https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/) | [] | [C++](1356-Sort-Integers-by-The-Number-of-1-Bits/cpp-1356/) | | |
937937
| 1357 | [Apply Discount Every n Orders](https://leetcode.com/problems/apply-discount-every-n-orders/) | [] | [C++](1357-Apply-Discount-Every-n-Orders/cpp-1357/) | | |
938938
| 1358 | [Number of Substrings Containing All Three Characters](1358-Number-of-Substrings-Containing-All-Three-Characters/cpp-1358/) | [] | [C++](1358-Number-of-Substrings-Containing-All-Three-Characters/cpp-1358/) | | |
939-
| | | | | | |
939+
| 1359 | [Count All Valid Pickup and Delivery Options](https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/) | [] | [C++](1359-Count-All-Valid-Pickup-and-Delivery-Options/cpp-1359/) | | |
940940
| 1360 | [Number of Days Between Two Dates](https://leetcode.com/problems/number-of-days-between-two-dates/) | [] | [C++](1360-Number-of-Days-Between-Two-Dates/cpp-1360/) | | |
941941
| 1361 | [Validate Binary Tree Nodes](https://leetcode.com/problems/validate-binary-tree-nodes/) | [] | [C++](1361-Validate-Binary-Tree-Nodes/cpp-1361/) | | |
942942
| 1362 | [Closest Divisors](https://leetcode.com/problems/closest-divisors/) | [] | [C++](1362-Closest-Divisors/cpp-1362/) | | |

0 commit comments

Comments
 (0)