C++ short O(n) time, O(1) space DP solution


  • 0
    M
        int findDerangement(int n) {
            if(n<=1) return 0;
            const int di=pow(10, 9)+7;
            long dp0=0, dp1=1, dp=1;
            for(int i=3;i<=n;i++) {
                dp=((i-1)*dp1+(i-1)*dp0)%di;
                dp0=dp1, dp1=dp;
            }
            return dp;
        }

Log in to reply
 

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