Java DP solution for reference


  • 2
    M

    A Java DP solution runs on
    K: number of flowers to plant
    N: length of flower bed
    O(K) space, O(NK) time

    //dp
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        //dp[i][j]: can put j flowers in first i place, i, j starting from 1
        //dp[i][j] = 
        //          dp[i-1][j] || dp[i-2][j-1], if flower[i] == 0 
        //          dp[i-2][j], if flower[i] == 1
        
        //nothing to plant
        if (n == 0) {
            return true; 
        } 
        
        //no place to plant
        if (flowerbed.length == 0) {
            return false;
        }
        
        boolean[][] dp = new boolean[3][n+1];
        dp[0][0] = true;
        
        //init: first j flowers put into non-space
        for (int j = 1; j <= n; j++) {
            dp[0][j] = false;
        }
        
        //init: first j flowers put into first space
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j == 1 && flowerbed[j-1] == 0;
        }
        
        //init: no flowers put into first i space
        for (int i = 1; i < 3; i++) {
            dp[i][0] = true;
        }
        
        //dp
        for (int i = 2; i <= flowerbed.length; i++) {
            for (int j = 1; j <= n; j++) {
                if (flowerbed[i-1] == 0) {
                    dp[i%3][j] = dp[(i-1)%3][j] || dp[(i-2)%3][j-1] && flowerbed[i-2] == 0;
                } else {
                    dp[i%3][j] = dp[(i-2)%3][j];
                }
                
                //System.out.println(i + ":" + j + ": " + dp[i%3][j]);
                
            }
        }
        
        return dp[flowerbed.length % 3][n];
    }

  • 1
    B

    great dp solution


  • 0
    K

    @mylemoncake

    can you explain the solution?
    what is your thought's in implementing it?


Log in to reply
 

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