day45【代码随想录】动态规划之完全平方数、单词拆分、打家劫舍、打家劫舍 II

---

前言

1、完全平方数
2、单词拆分
3、打家劫舍
4、打家劫舍 II

---

一、完全平方数（力扣279）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

分析：
每一个元素可以重复使用----完全背包问题
每一个物品并没有直接放进数组 每一个物品都是完全平方数 1 、4、9、16、25、36……
组合数不是排列数 ---->外层循环物品 内层循环背包
本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

class Solution {public int numSquares(int n) {int[] nums = new int[101];for(int i=1;i<nums.length;i++){nums[i] = i*i;}int max = Integer.MAX_VALUE;int[] dp = new int[n+1];//初始化for (int j = 0; j <= n; j++) {dp[j] = max;}dp[0] = 0;for(int i=1;i<nums.length;i++){for(int j=1;j<=n;j++){if(j>=nums[i])dp[j] = Math.min(dp[j],dp[j-nums[i]]+1);}}return dp[n];}
}

二、单词拆分（力扣139）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

分析：
可以重复使用字典中的单词---->完全背包问题
排列数---->外层循环背包、内层循环物品（单词）

1、dp[j]数组以及含义
dp[j] ：j是字符串s的长度 dp[j] = true表示可以由wordDict拼接而成
2、递推公式
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true
if([j,i] && dp[j]==true) dp[i] = true;
3、初始化
dp[0] = true; 其他非零下标全部初始为false
4、遍历顺序
外层循环背包、内层循环物品（单词）

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] valid = new boolean[s.length()+1];valid[0] = true;for(int j=1;j<=s.length();j++){for(int i=0;i<j && !valid[j];i++){//截取字符串长度if(set.contains(s.substring(i,j)) && valid[i])valid[j] = true;}}return valid[s.length()];}
}

三、打家劫舍（力扣198）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

分析：
当前的状态我是偷还是不偷呢？
当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。

1、确定dp数组以及下标的含义
dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2、确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷。

• 如果偷第i房间，dp[i] = dp[i - 2] + nums[i] ，第i-1房是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
• 如果不偷第i房间，dp[i] = dp[i-1]; 即考虑i-1房

dp[i] 取最大值，dp[i] = Math.max[dp[i-1], dp[i-2]+nums[i] ];

3、dp数组初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

4、遍历顺序
从前往后

class Solution {public int rob(int[] nums) {int[] dp = new int[nums.length];if (nums.length == 1) return nums[0];//初始化dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);//遍历for(int i=2;i<nums.length;i++){dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.length-1];}
}

四、打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

分析：
与上一题相比 区别在于成环了

成环的话主要有如下三种情况：

• 情况一：考虑不包含首尾元素
  

• 情况二：考虑包含首元素，不包含尾元素
  

• 情况三：考虑包含尾元素，不包含首元素
  
  情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
  计算出情况二和情况三的值，最后取较大值即可。

class Solution {public int rob(int[] nums) {int len =nums.length;if(nums==null||len==0) return 0;if(len==1) return nums[0];return Math.max(robI(nums,0,len-1),robI(nums,1,len));}int robI(int[] nums,int start,int end) {int x=0,y=0,z=0;for(int i=start;i<end;i++){y=z;  //y: i-1z=Math.max(y,x+nums[i]);//z: ix=y; //x: i-2;}return z;}
}

---