Skip to content

Commit 9153ced

Browse files
committed
1259 solved.
1 parent d080445 commit 9153ced

File tree

3 files changed

+47
-0
lines changed

3 files changed

+47
-0
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.24)
2+
project(cpp_1259)
3+
4+
set(CMAKE_CXX_STANDARD 17)
5+
6+
add_executable(cpp_1259 main.cpp)
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/// Source : https://leetcode.com/problems/handshakes-that-dont-cross/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2023-02-22
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// DP
12+
/// Time Complexity: O(n^2)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
16+
private:
17+
const long long MOD = 1e9 + 7;
18+
19+
public:
20+
int numberOfWays(int numPeople) {
21+
22+
vector<long long> dp(numPeople + 1, 0);
23+
dp[0] = 1;
24+
for(int i = 2; i <= numPeople; i ++){
25+
if(i % 2) continue;
26+
for(int j = 1; j < i; j ++){
27+
int len = j - 1;
28+
if(len & 1) continue;
29+
dp[i] += dp[len] * dp[i - (len + 2)] % MOD;
30+
}
31+
dp[i] %= MOD;
32+
}
33+
return dp.back();
34+
}
35+
};
36+
37+
int main() {
38+
39+
return 0;
40+
}

readme.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1226,6 +1226,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
12261226
| 1251 | Database Problem: [Link](https://github.com/liuyubobobo/Play-Leetcode-Database/) | - | - | - | - |
12271227
| 1252 | [Cells with Odd Values in a Matrix](https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/) | [] | [C++](1001-1500/1252-Cells-with-Odd-Values-in-a-Matrix/cpp-1252/) | | |
12281228
| | | | | | |
1229+
| 1259 | [Handshakes That Don't Cross](https://leetcode.com/problems/handshakes-that-dont-cross/description/) | [] | [C++](1001-1500/1259-Handshakes-That-Dont-Cross/cpp-1259/) | | |
12291230
| 1260 | [Shift 2D Grid](https://leetcode.com/problems/shift-2d-grid/) | [solution](https://leetcode.com/problems/shift-2d-grid/solution/) | [C++](1001-1500/1260-Shift-2D-Grid/cpp-1260/) | | |
12301231
| 1261 | [Find Elements in a Contaminated Binary Tree](https://leetcode.com/contest/weekly-contest-163/problems/find-elements-in-a-contaminated-binary-tree/) | [C++](1001-1500/1261-Find-Elements-in-a-Contaminated-Binary-Tree/cpp-1261/) | | | |
12311232
| 1262 | [Greatest Sum Divisible by Three](https://leetcode.com/problems/greatest-sum-divisible-by-three/) | [] | [C++](1001-1500/1262-Greatest-Sum-Divisible-by-Three/cpp-1262/) | | |

0 commit comments

Comments
 (0)