算法学习day31（动态规划）

一、比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

输入：n = 2
输出：[0,1,1]
解释：0 --> 0 1 --> 1 2 --> 10

思路一： 如果是偶数的话，1的个数和它的一半是相同的；如果是奇数的话，1的个数等于它前面那个偶数的个数+1

代码:

int countBits(int num) {int[] res=new int[num+1]result[0] = 0;for(int i = 1; i <= num; i++){if(i%2==0)res[i]=res[i/2];else res[i]=res[i-1]+1;}return result;}

思路二：遇到一个数，想办法把它拆成 最靠近它的2的幂 和另一个数

eg:7拆成4和3 4中1的个数有1个，3中1的个数有2个 所以res[7]=res[4]+res[3]

如果遇到2的幂次，dp[i]=1;

代码：

  public int[] countBits(int n) {int[] dp = new int[n + 1];dp[0] = 0;int x = 1;for (int i = 1; i <= n; i++) {// 如果是2的幂，只有最高位为1if (i == x) {dp[i] = 1;x *= 2;} else {// 如果不是2的幂，则为取模最高位后的值+1// 例如 5 % 4 = 1， 那么就是4+1也就是 101；也就是1+dp[1]; int mod = i % (x / 2);dp[i] = 1 + dp[mod];//1代表的是2的幂，dp[mod]代表的是剩下的那个数的1的值}}return dp;}

二、打家劫舍/打家劫舍II（二刷 dp）

题意：小偷要偷窃，相邻房屋是不能偷窃的，否则就会发出报警信号。给定一个数组nums，表示每个房间的价值，第一个房屋和最后一个房屋是相邻的，给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

思路：

因为房屋是相邻的，所以要破除这个环，那么应该如何破除？因为首尾是相连的，所以我们只需要考虑两种情况：偷首就不能偷尾；偷尾就不能偷首

那我们就把两种情况分别可以偷窃到的最高金额计算出来，比较之后返回。

那么如何计算偷窃道德最高金额？动态规划。

一间屋子可以偷也可以不偷，偷的话dp[i]=dp[i-2]+nums[i];不偷的话:dp[i]=dp[i-1]

dp[i]:偷窃到第i间房子所偷窃的最大价值

递推公式：dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);

初始化：dp[0]=nums[0],dp[1]=Math.max(nums[0],nums[1]);

遍历顺序：从i=2开始

代码:

class Solution {public int rob(int[] nums) {if(nums.length<=1)return nums[0];//如何破环int part1=getMax(nums,0,nums.length-2);int part2=getMax(nums,1,nums.length-1);return Math.max(part1,part2);}public int getMax(int[] nums,int left,int right){if(right==left)return nums[left];int[] dp=new int[right-left+1];dp[0]=nums[left];dp[1]=Math.max(nums[left],nums[left+1]);for(int i=left+2;i<=right;i++){dp[i-left]=Math.max(dp[i-2-left]+nums[i],dp[i-1-left]);}return Math.max(dp[dp.length-1],dp[dp.length-2]);}
}

三、两个键的键盘(dp)

最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：

• Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
• Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

思路：

如何才可以得到n个‘A’？可以根据因数来做。

eg:n=12; 可以是6个A CopyAll->Paste之后得到12个A

也可以是3个A CopyAll->Paste3次后得到12个A

还可以是2个A CopyAll->Paste5次后得到12个A

如果是质数的话，那么操作的次数就是它本身，需要CopyAll+Paste(n-1)次

所以就是在它的因数里面找最小操作次数。双循环

代码：

class Solution {public int minSteps(int n) {//dp[i]的定义：打印出i个A字符需要的操作次数int[] dp=new int[n+1];//dp初始化dp[1]=0;//遍历数组for(int i=2;i<=n;i++){dp[i]=i;for(int j=2;j<=Math.sqrt(i);j++){if(i%j==0){dp[i]=Math.min(dp[i],dp[j]+i/j);dp[i]=Math.min(dp[i],dp[i/j]+j);}}}return dp[n];}
}

四、解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

"1" -> 'A'  "2" -> 'B'  "25" -> 'Y'  "26" -> 'Z'

然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

思路：这道题是爬楼梯类似。但是比爬楼梯要多个决定条件。

给定一串字符串。

如果该数字不等于0，那么就可以只切割该字符，此时dp[i+1]=dp[i];   和爬楼梯从下一层爬到该层一样;

在上一个条件的基础上，如果该数字可以和前一个数字组成一个合法的字符（>=10&&<=26），那么就可以从下两层爬到该层(一次爬两个)。此时dp[i+1]+=dp[i-1];

动态规划五部曲：

1.dp[i]:代表的含义是：字符串中以i-1为结尾的字串的切割方法有多少种。dp.length=s.length()+1

2.递推公式：

    2.1如果和上一个数字无法组成合法的大写字母:dp[i+1]=dp[i];

    2.2 如果和上一个数字可以组成合法的大写字母:dp[i+1]=dp[i]+dp[i-1]

3.初始化:dp[0]=dp[1]=1; 默认空串也有一种切割方式。

eg:226。遍历到index=1的时候，可以组成一个合法的大写字母。dp[i+1]=dp[i]+dp[i-1]。这里的dp[i-1]就代表着22

代码：

class Solution {public int numDecodings(String s) {int size=s.length();int[] dp=new int[size+1];dp[0]=1;//初始化 dp[1]=1;//dp[i]表示的是字符串中以(i-1)为结尾的字串 有多少种切割方式if(s.charAt(0)=='0')return 0;for(int i=1;i<size;i++){char ch1=s.charAt(i);if(ch1-'0'!=0){dp[i+1]+=dp[i];}char ch2=s.charAt(i-1);//如果这两个数字可以组成一个有效的大写字母if((ch2-'0')*10+(ch1-'0')>=10&&(ch2-'0')*10+(ch1-'0')<=26){dp[i+1]+=dp[i-1];}}return dp[size];}
}