Dynamic programming Java with comment


  • 0
    T
    public class Solution {
        /*Dynamic programming.
        * OPT[k] stands for the maximum number of flowers we can plant in the first k plots of flowerbed.
        * If flower[k] == 0
        *   If flowerbed[k-1] == 0
        *     OPT[k] = max(OPT[k-1], OPT[k-2]+1)
        *   Else
        *     OPT[k] = OPT[k-1]
        * Else
        *   OPT[k-1] = OPT[k-2]
        *   OPT[k] = OPT[k-2]
        */
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            if (n == 0) return true;
            if (flowerbed.length == 0) return false;
            int[] opt = new int[flowerbed.length];
            if(flowerbed[0] == 0)   opt[0] = 1;
            for(int i = 1; i < flowerbed.length; i++){
                if(flowerbed[i] == 0){
                    if(flowerbed[i-1] == 0){
                        int temp1 = opt[i-1];
                        int temp2 = 0;
                        if(i-2>=0)  temp2 = opt[i-2];
                        opt[i] = Math.max(temp1, temp2+1);
                    }
                    else{
                        opt[i] = opt[i-1];
                    }
                }
                else{
                    int temp2 = 0;
                    if(i-2>=0)  temp2 = opt[i-2];
                    opt[i-1] = temp2;
                    opt[i] = temp2;
                }
            }
            if(opt[flowerbed.length-1] >= n)    return true;
            else    return false;
        }
    }
    

Log in to reply
 

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