【LeetCode 983】门票的最低费用 Minimum Cost For Tickets

小咪咪 2021-09-22 22:28 248阅读 0赞

题目：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]  
即，给定一个数组代表你一年中的什么时候会去电影院，给定另外一个数组代表一日票，七日票，跟三十日票的金额，要求出如何买票，才能使花费最少。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][20190317151545614.png]  
思路：  
明显看出这个是一个动态规划的题目，因此我需要两步曲来完成，首先是`状态的定义`，我们发现，比如 days\[1,2,3,5\]，我们要输出的是第5天所花费的最少金额，而且 days是严格递增的，所以我们只要求出第`days[days.length - 1]`的花费就OK，因此可以定义状态`dp[days[days.length - 1]]`。  
定义好了状态，第二步就是看状态的转移方程，由于我们定义的状态是天数，我们需要做的，就是从第0天的花费，递推到第days\[days.length - 1\]天的花费，而对于每一天，只有两种情况：  
① 这一天不去看电影，则到达这一天的花费dp\[i\]为：`dp[i] = dp[i - 1]`，跟前一天的花费是相同的  
② 这一天去看电影，则我们要判断这一天需要买什么票，哪种票更合适，即我们判断我们是买一日票，还是过去七天用七日票，还是过去三十天用三十日票的总花费更低，因此判断`dp[i - 1] + costs[0], dp[i - 7] + costs[1]), dp[i - 30] + costs[2])` 这三个数哪个最小，赋值为当前的dp\[i\]

代码：

public int mincostTickets(int[] days, int[] costs) { 
        	// 判断输入是否合法
            if (days == null || costs == null || costs.length != 3 || days.length == 0) return 0;
    
    		// 状态的定义
            int[] dp = new int[days[days.length - 1] + 1];
            
    		// 将有观影的时间点存入到 set中，便于判断
    		Set<Integer> set = new HashSet<>();
            for (int day : days
                 ) { 
                set.add(day);
            }
    
    		// 从第 day[0]天开始遍历，因为前面几日都无观影，花费为 0
            for (int i = days[0]; i < dp.length; i++) { 
                if (set.contains(i)) { 
                    dp[i] = Math.min(Math.min(helper(dp, i - 1) + costs[0], helper(dp, i - 7) + costs[1]),
                            helper(dp, i - 30) + costs[2]);
                } else { 
                    dp[i] = dp[i - 1];
                }
            }
            return dp[days[days.length - 1]];
        }
    
    	// 处理判断七日票跟三十日票时，可能出现数组越界的情况
        private int helper(int[] dp, int i) { 
            if (i <= 0)
                return 0;
            return dp[i];
        }

在 LeetCode上提交结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/5faab275997645a48ade77310e439649.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190317151528791.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n,size_16,color_FFFFFF,t_70
[20190317151545614.png]: /images/20210920/9ef56288f42346788fe2c13146c0b42c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]: /images/20210920/09e262cdbe8f4660ab23636da520f868.png
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html