605. 种花问题 - 力扣(LeetCode)
动态规划
bool canPlaceFlowers(vector<int>& flowerbed, int n)
int m = flowerbed.size();
if(1 == m)return !flowerbed[0] >= n;
else if(2 == m)return ((!flowerbed[0] && !flowerbed[1]) >= n);
memset(dp, 0, sizeof dp);
if(!flowerbed[0] && !flowerbed[1])
dp[1][1] = 1 - flowerbed[2];
for(int i = 2; i < m - 1; i++)
if(!flowerbed[i] && !flowerbed[i + 1] && !flowerbed[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + 1);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]);
dp[i][0] = max(dp[i - 1][1], dp[i - 2][1]);
if(!flowerbed[m - 1] && !flowerbed[m - 2])
dp[m - 1][1] = max(dp[m - 2][0] + 1,dp[m - 2][0]);
dp[m - 1][0] = max(dp[m - 1][1], dp[m - 2][1]);
dp[m - 1][0] = max(dp[m - 2][1],dp[m - 2][0]);
return max(dp[m - 1][0], dp[m - 1][1]) >= n;
贪心
bool canPlaceFlowers(vector<int> &flowerbed, int n)
int m = flowerbed.size();
flowerbed.insert(flowerbed.begin(),0);
flowerbed.emplace_back(0);
for(int i = 1; i <= m; i++)
if(!flowerbed[i] && !flowerbed[i - 1] && !flowerbed[i + 1])