DP with O(1) space using rolling array


  • 0
    S

    Think this problem as filling n numbers to n positions and the only restriction is that number i can't fill position i. The recursive relationship can be derived as follows. First, there are n-1 choices for position 1. Suppose that we choose number i (not 1) to fill position 1. Then there are two following situations: (1) If we choose number 1 to fill position i, then the subproblem becomes filling n-2 numbers into n-2 position with the same restriction as before. (2) If we do not choose number 1 to fill position i, then the subproblem becomes filling n-1 numbers to n-1 positions with the same restriction as before. Therefore, the recursive relationship is : dp[i] = (i-1) * (dp[i-2] + dp[i-1]).

    A straight forward solution can use O(N) space. However, when looking at the recursive relationship, we can see that step i only depends on previous two steps i - 1 and i - 2. This indicates that we can use constant space to optimize the space complexity. There are many ways to achieve this space optimization. I think "rolling array" is very easy to understand and can be easily implemented.

    We first declare an array with size 2. Then the recursive relationship can be modified as dp[i%2] = (i-1) * (dp[(i-2)%2] + dp[(i-1)%2]). Finally, the solution is stored at dp[n%2]. This "rolling array" approach can also be used to optimize the space complexity of two dimensional DP problems from O(M*N) to O(N) or O(M), if the solutions of current row (column) only depends on the solutions of previous row (column). The code for this de-arrangement problem is as follows:

    public class Solution {
        private static final int MOD = (int)1e9 + 7;
        public int findDerangement(int n) {
            long[] dp = new long[2];
            dp[0] = 1;
            dp[1] = 0;
            for (int i = 2; i <= n; i++) {
                dp[i%2] = ((i-1) * (dp[(i-1)%2] + dp[(i-2)%2])) % MOD;
            }
            return (int) dp[n%2];
        }
    }
    

Log in to reply
 

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