LeetCode刷题 day20

1. 最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：
输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, …, 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：
输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, …, 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
你总共花了 $17，并完成了你计划的每一天旅行。

思路
本题采用动态规划来解题。动态规划类题目一般都是从递归入手，一步一步优化成严格位置依赖的动态规划解法。
递归算法：
当来到days[i]时，有三种选择，可以选择1,7,30天的通行证，那么只需求出每种情况的最小消费即可，然后再从这三个选择最小值，针对每张通行证，需要覆盖尽可能多的旅游天数。代码如下

classSolution{privatestaticint[]durations={1,7,30};publicintmincostTickets(int[]days,int[]costs){returnf1(days,costs,0);}publicintf1(int[]days,int[]costs,intstart){if(start==days.length){return0;}intminCost=Integer.MAX_VALUE;//分三种情况，1,7,30for(inti=0;i<costs.length;i++){intduration=durations[i];intj=start;while(j<days.length&&days[j]-days[start]<duration){j++;}minCost=Math.min(minCost,costs[i]+f1(days,costs,j));}returnminCost;}}

提交后通过37/70个测试用例，说明递归思路没有问题，代码需要继续优化
记忆化搜索：
不难发现，当选择1,7,30天的通行证后，势必会在后面的某个时间点继续往后递归调用，假如用一个缓存保存days[i]往后的最优方案，那调用时只用计算一次即可，不用反复计算，这样会大大缩短时间复杂度，因此得到记忆化搜索的算法

classSolution{privatestaticint[]durations={1,7,30};intn;publicintmincostTickets(int[]days,int[]costs){n=days.length;int[]dp=newint[n+1];Arrays.fill(dp,-1);returnf1(days,costs,0,dp);}publicintf1(int[]days,int[]costs,intstart,int[]dp){if(start==n){return0;}if(dp[start]!=-1){returndp[start];}intminCost=Integer.MAX_VALUE;for(inti=0;i<costs.length;i++){intduration=durations[i];intj=start;while(j<n&&days[j]-days[start]<duration){j++;}minCost=Math.min(minCost,costs[i]+f1(days,costs,j,dp));}dp[start]=minCost;returnminCost;}}

此时，通过全部测试用例，并且时间复杂度已最优，但还不是动态规划解法。
动态规划：
上述记忆化搜索过程是在递归中加入缓存，需转化成严格位置依赖的动态规划。通过上述思考过程可知，可以从后往前计算，不用递归调用。

classSolution{privatestaticint[]durations={1,7,30};publicintmincostTickets(int[]days,int[]costs){intn=days.length;int[]dp=newint[n+1];Arrays.fill(dp,0,n+1,Integer.MAX_VALUE);dp[n]=0;for(intk=n-1;k>=0;k--){intj=k;for(intl=0;l<3;l++){while(j<n&&days[j]-days[k]<durations[l]){j++;}dp[k]=Math.min(dp[k],costs[l]+dp[j]);}}returndp[0];}}

时间复杂度：O(n) n是数组长度
空间复杂度：O(n)

2.解码方法

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

“1” -> ‘A’

“2” -> ‘B’

…

“25” -> ‘Y’

“26” -> ‘Z’

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

例如，“11106” 可以映射为：

“AAJF” ，将消息分组为 (1, 1, 10, 6)
“KJF” ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 “06” 不是一个合法编码（只有 “6” 是合法的）。
注意，可能存在无法解码的字符串。

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

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：
输入：s = “12”
输出：2
解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

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

示例 3：
输入：s = “06”
输出：0
解释：“06” 无法映射到 “F” ，因为存在前导零（“6” 和 “06” 并不等价）。

思路
递归算法：
先从递归入手，当前数字分为可单独解码和不可单独解码两种情况：
若数字为0，则不能单独解码，从当前到最后解码情况为0种；
若数字为1，则可单独解码，也可与后面一位数字一起解码
若数字为2，则可单独解码，若后一位数字小于7，则可一起解码
若数字大于2，则只能单独解码

classSolution{publicintnumDecodings(Strings){char[]s1=s.toCharArray();returnf1(s1,0);}publicintf1(char[]s,intstart){if(start==s.length){return1;}if(start>s.length||s[start]=='0'){return0;}intans=0;if(start+1<s.length&&(s[start]-'0')*10+s[start+1]-'0'<=26){ans+=f1(s,start+2);}ans+=f1(s,start+1);returnans;}}

测试用例通过23 / 269 ，最后一个超出时间限制，表明当前递归算法思路正确，时间复杂度需要优化
记忆化搜索算法：
从递归往下推不难看出，s[i,n-1]串的结果依赖s[i+1,n-1]和s[i+2,n-1]子串的解码结果，因此用缓存保存后续子串解码方案，则减少了重复计算过程

classSolution{publicintnumDecodings(Strings){returnnumDecodings(s.toCharArray(),0);}privateintnumDecodings(char[]s,inti){intn=s.length;intcur=0;intnext=1;intnextnext=0;for(intj=n-1;j>=0;j--){if(s[j]=='0'){cur=0;}else{cur=next;if(j+1<n&&(s[j]-'0')*10+s[j+1]-'0'<=26){cur+=nextnext;}}nextnext=next;next=cur;cur=0;}returnnext;}}

严格位置依赖的动态规划：

classSolution{publicintnumDecodings(Strings){char[]s1=s.toCharArray();intn=s1.length;int[]dp=newint[n+1];dp[n]=1;for(inti=n-1;i>=0;i--){if(s1[i]=='0'){dp[i]=0;continue;}dp[i]+=dp[i+1];if(i+1<n&&(s1[i]-'0')*10+s1[i+1]-'0'<=26){dp[i]+=dp[i+2];}}returndp[0];}}

时间复杂度：O(n) n是字符串长度
空间复杂度：O(n)
当前算法还可以继续优化，从动态规划解法可知，dp[i]只依赖dp[i+1]和dp[i+2]，因此可用两个局部变量代替dp数组，此处不再给出具体解法