Advertisement
humbertoyusta

dp-connected-components

Jul 6th, 2021
1,378
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.54 KB | None | 0 0
  1. n = int(input())
  2.  
  3. DP = []
  4. for i in range(n+2):
  5.     dp_row = [0] * (n+2)
  6.     DP.append(dp_row)
  7.  
  8. DP[1][1] = 1
  9.  
  10. for i in range(1,n):
  11.     for j in range(1,i+1):
  12.  
  13.         # Create a new component
  14.         DP[i+1][j+1] += DP[i][j] * ( j + 1 )
  15.        
  16.         # Add at the beggining or the end of a component
  17.         DP[i+1][j] += DP[i][j] * ( 2 * j )
  18.        
  19.         # Merge two existing components
  20.         DP[i+1][j-1] += DP[i][j] * ( j - 1 )
  21.  
  22. print( DP[n][1] )
  23. # Isn't this the most amazing code to compute n! you've ever seen :)
  24.  
  25.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement