【每日算法Day 35】动态规划基础3
动态规划相关的题目还是一句话：发现可能不明显的状态与状态转移方程。还有些题目的边界情况的初始化可能会考验你的细心程度与心态2333
# LeetCode 198. 打家劫舍 (opens new window)
# 题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
# 示例
输入：[100,7,2,9,3,1]
输出：110
解释：
偷窃 1 号房屋 (金额 = 100), 偷窃 4 号房屋 (金额 = 9)，接着偷窃 6 号房屋 (金额 = 1)。
偷窃到的最高金额 = 100 + 9 + 1 = 110 。
2
3
4
5
# 解题思路
记f(n)为取第n位数字时能偷到的最高金额，则由于f(n-1)不能取，则对于一般的输入f(n)=Max(f(n-2),f(n-3))+nums(n)。这就是状态转移方程，最后注意下初始化的边界情况即可。
public int rob(int[] nums) {
if (nums==null||nums.length==0) return 0;
int n=nums.length;
if(n==1) return nums[0];
for (int i = 2; i < n; i++) {
if (i == 2) {
nums[i] += nums[0];
} else {
nums[i]+=Math.max(nums[i-2],nums[i-3]);
}
}
return Math.max(nums[n-1],nums[n-2]);
}
2
3
4
5
6
7
8
9
10
11
12
13
官方题解的状态f(n)指的是偷前n家能偷到的最高金额（不一定取最后第n家），则状态转移方程写为f(n)=Max(f(n-2)+nums(n),f(n-1))。
public int rob(int[] nums) {
if (nums==null||nums.length==0) return 0;
int n=nums.length;
if(n==1) return nums[0];
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
}
2
3
4
5
6
7
8
9
10
11
12
# LeetCode 213. 打家劫舍 II (opens new window)
# 题目描述
在上一题的基础上，新增下面的限制后，该如何计算？
- 这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。
# 示例
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
2
3
# 解题思路
在前面一题的基础上，新增了第一个和最后一个不能同时选择，那么可以分别对nums[0,n-1]和nums[1,n]进行动态规划，取得二者的最大值就是最终的解。
public int rob(int[] nums) {
if (nums==null||nums.length==0) return 0;
int n=nums.length;
if(n==1) return nums[0];
return Math.max(rob2(Arrays.copyOfRange(nums,0,nums.length-1)),rob2(Arrays.copyOfRange(nums,1,nums.length)));
}
private int robb(int[] nums) {
if (nums==null||nums.length==0) return 0;
int n=nums.length;
if(n==1) return nums[0];
for (int i = 2; i < n; i++) {
if (i == 2) {
nums[i] += nums[0];
} else {
nums[i]+=Math.max(nums[i-2],nums[i-3]);
}
}
return Math.max(nums[n-1],nums[n-2]);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# LeetCode 91. 解码方法 (opens new window)
# 题目描述
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
2
3
4
给定一个只包含数字的非空字符串，请计算解码方法的总数。
# 示例
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
2
3
# 解题思路
一般情况下，记前n位的字符串有f(n)种解码方法，则对于前n+1位字符串，如果第n位和第n+1位合起来可以被解码，那么f(n+1)=f(n-1)+f(n)，否则f(n+1)=f(n)即状态转移方程为：
f(n)=f(n-1)，最后两位合起来不能被解码
=f(n-1)+f(n-2)，最后两位合起来可以被解码
2
初始化边界情况，f(1)=1,f(2)=1（不能被解码）或2（能被解码）。
（分割线）设计的时候很简单，但是编码的时候发现有一个0的问题例如"01","100"这样的需要特别注意，所以状态转移方程写成下面这样子。。原因在于题目的设计中单个0不能直接解码为一个字符，而"10""20"却是可以的，所以需要小心设计验证方法。真的挺坑的，如果是从0开始编码就不存在这个问题。
public int numDecodings(String s) {
if(s==null||s.length()==0|| toInt(s.charAt(0))==0) return 0;
int n=s.length();
if(n==1) return 1;
int[] dp=new int[n];
dp[0]=1;
int a=toInt(s.charAt(0)),b=toInt(s.charAt(1));
if (match2(a, b) && match1(b)) {
dp[1]=2;
} else if (!match2(a, b) && !match1(b)) {
dp[1]=0;
}else{
dp[1]=1;
}
if (n==2) return dp[1];
for (int i = 2; i < n; i++) {
int curr=toInt(s.charAt(i)),curr_1=toInt(s.charAt(i-1));
if (match1(curr)) {
if (match2(curr_1, curr)) {//e.g. [1,2,2,...]
dp[i] = dp[i - 1] + dp[i - 2];
} else {//e.g. [1,6,2,...]
dp[i] = dp[i - 1];
}
} else {
if (match2(curr_1, curr)) {//e.g. [1,2,0,...]
dp[i] = dp[i - 2];
} else {//e.g. [1,6,0,...]
dp[i]=0;
}
}
}
return dp[n-1];
}
private int toInt(char c){
return (int)c-'0';
}
private boolean match2(int a, int b){
int tmp=a*10+b;
return tmp>=10&&tmp<=26;
}
private boolean match1(int a){
return 0<a&&9>=a;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48