力扣2道dp

198. 打家劫舍 - 力扣（LeetCode）

设前i+1间房能搜刮到的最高金额为dp[i]

对于dp[i]，要么不更新，保持和dp[i-1]一样，要么更新，变为dp[i-2]+nums[i]。两者谁的值更大，决定是否更新。

class Solution 
{
public:int rob(vector<int>& nums) {int n=nums.size();if(n==1) return nums[0];vector<int>dp(n);//dp[i]表示前i+1间能搜刮的最高金额dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<n;i++){dp[i]=max(dp[i-1],nums[i]+dp[i-2]);}return dp[n-1];}
};

279. 完全平方数 - 力扣（LeetCode）

dp[i]表示最少需要多少个数的平方来表示整数i，显然这些数落在[1,sqrt(i)]内，我们可以枚举这些数。当枚举到j时，我们还需要取i-j^2，那么需要知道dp[i-j^2]，由于子问题与原问题类似，因此使用动态规划。

class Solution
{
public:int numSquares(int n){vector<int>dp(n+1);for (int i = 1; i < n; i++){int minn = INT_MAX;for (int j = 1; j * j <= i; j++){minn = min(minn, dp[i - j * j]);//找出dp[i-j*j]中最小的那个}dp[i] = minn + 1;}return dp[n];}
};