Skip to content

1259. Handshakes That Don't Cross 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int numberOfWays(int numPeople) {
    constexpr int kMod = 1'000'000'007;
    // dp[i] := the number of ways i handshakes could occure s.t. none of the
    // handshakes cross
    vector<long> dp(numPeople / 2 + 1);
    dp[0] = 1;

    for (int i = 1; i <= numPeople / 2; ++i)
      for (int j = 0; j < i; ++j) {
        dp[i] += dp[j] * dp[i - 1 - j];
        dp[i] %= kMod;
      }

    return dp[numPeople / 2];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int numberOfWays(int numPeople) {
    final long kMod = 1_000_000_007;
    // dp[i] := the number of ways i handshakes could occure s.t. none of the
    // handshakes cross
    long[] dp = new long[numPeople / 2 + 1];
    dp[0] = 1;

    for (int i = 1; i <= numPeople / 2; ++i)
      for (int j = 0; j < i; ++j) {
        dp[i] += dp[j] * dp[i - 1 - j];
        dp[i] %= kMod;
      }

    return (int) dp[numPeople / 2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def numberOfWays(self, numPeople: int) -> int:
    kMod = 1_000_000_007
    # dp[i] := the number of ways i handshakes could occure s.t. none of the
    # handshakes cross
    dp = [1] + [0] * (numPeople // 2)

    for i in range(1, numPeople // 2 + 1):
      for j in range(i):
        dp[i] += dp[j] * dp[i - 1 - j]
        dp[i] %= kMod

    return dp[numPeople // 2]