# Java DP solution for reference

• 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];
}``````

• great dp solution

• @mylemoncake

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

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