198
這道題可以用二維dp做，dp[i][0]表示第i間房偷按灶，dp[i][1]表示第i間房不偷筐咧，dp[i][0]=dp[i-1][1]+nums[i];dp[i][1]=max(dp[i-1][0],dp[i-1][1])。
279
這道題是背包類問題量蕊，可以把總和當(dāng)作背包的容量残炮，遍歷過程中每個(gè)序號的和當(dāng)作物品，dp數(shù)組表示裝入物品數(shù)的最小值势就。
class Solution {
public:
? ? int numSquares(int n) {
? ? ? ? vector<int> dp(n+1,INT_MAX);
? ? ? ? dp[0]=0;
? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? {
? ? ? ? ? ? for(int j=1;j*j<=i;j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? dp[i]=min(dp[i],dp[i-j*j]+1);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[n];
? ? }
};
322
這道題的解法和上面那道題是一樣的苞冯。
