Pythonでk個の重複しない線分のセットの数を見つけるプログラム

線上にn個の点があり、i番目の点（0からn-1まで）が位置x =iにあるとすると、それぞれがセグメントは2つ以上のポイントをカバーします。各線分の端点は、整数の座標を持っている必要があります。 k線分は、指定されたn点すべてをカバーする必要はなく、端点を共有できます。答えが大きすぎる場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がn =4 k =2の場合、5つの可能性を作成できるため、出力は5になります[（0から2）、（2から3）]、[（0から1）、（1から3）]、[（0 to 1）、（2 to 3）]、[（1 to 2）、（2 to 3）]および[（0 to1）、（1 to 2）]

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7
• n：=n-1
• 関数dp（）を定義します。これには、i、covered、jが必要です
• iがnと同じ場合、
  • jがkと同じ場合はtrueを返し、それ以外の場合はfalseを返します
• j> kの場合、
• ans：=dp（i + 1、False、j）+ dp（i + 1、True、j + 1）
• カバーされている場合は、
  • ans：=ans + dp（i + 1、True、j）
• return ans mod m
• メインメソッドからdp（0、False、0）を返します

例

理解を深めるために、次の実装を見てみましょう-

def solve(n, k):
   m = 10 ** 9 + 7
   n -= 1

   def dp(i, covered, j):
      if i == n:
         return j == k
      if j > k:
         return 0
      ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1)
      if covered:
         ans += dp(i + 1, True, j)
      return ans % m

   return dp(0, False, 0)

n = 4
k = 2
print(solve(n, k))

入力

4, 2

出力

5