[Go] O(n) Dynamic programming


  • 0
    Z
    func findDerangement(n int) int {
        
        dp := [1000000+1][2]int{}
        
        
        dp[1][0] = 0 // 1 element along with 0 free element
        dp[1][1] = 1 // 1 element along with 1 free element
        // free element: we can place it anywhere because its own position has already been occupied
        
        for i := 2; i <= n; i++ { // i -> n
            dp[i][0] = (i - 1) * dp[i-1][1] // consider the last element, we can place it on any preceding position, with introducing 1 free element (whose position is occupied by the last element)
            dp[i][0] %= 1000000007
            // For dp[i][1], we have i positions, i-1 for non-free element (non free space), 1 for free element (free space)
            // dp[i-1][0]: place free element on "free space"
            // dp[i-1][1]: place free element on "non-free space" 
            dp[i][1] = dp[i-1][0] + (i - 1) * dp[i-1][1] 
    
            dp[i][1] %= 1000000007
        }
        
        return dp[n][0]
      
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.