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