JavaCodeMing
diff --git a/‎Algorithm/983.最低票价(中等).md‎
Lines changed: 52 additions & 0 deletions b/‎Algorithm/983.最低票价(中等).md‎
Lines changed: 52 additions & 0 deletions
@@ -0,0 +1,52 @@
+```text
+题目: 
+    days数组保存1到365的整数,表示一年的第几天需要出行,
+    costs数组分别保存了购买为期1天、7天、30天通行证的金额,
+    返回你想要完成在给定的列表days中列出的每一天的旅行所需要的最低消费;
+        输入：days = [1,4,6,7,8,20], costs = [2,7,15]
+        输出：11
+        (第1天买一张为期1天的,第4天买一张为期7天的,第20天买一张为期1天的)
+1.动态规划:
+    [1]思路: 第i天到365天的最少费用等于第i天的花费cost(j)加上第i+j天到365天的最少花费;(j为三种通行证的有效期,j∈{1,7,30})
+        (1)根据需求构建动态规划转移方程: dp(i)=min{cost(j)+dp(i+j)} j∈{1,7,30}
+    [2]实现:
+        // 定义一个哈希表用来存储出行的天
+        Set<Integer> set;
+        // 定义一个数组来保存第i天到365天对应花费的钱
+        Integer[] memo;
+        int[] costs;
+        public int mincostTickets(int[] days, int[] costs) {
+            set = new HashSet<>();
+            memo = new Integer[366];
+            this.costs = costs;
+            // 将需出行的天放入到哈希表中
+            for (int day : days) {
+                set.add(day);
+            }
+            // 动态规划转移方程: dp(i)=min{cost(j)+dp(i+j)} j∈{1,7,30}
+        return dp(1);
+        }
+        private int dp(int i) {
+            if (i > 365) {
+                return 0;
+            }
+            // 说明第i天以后的花费金额都计算出来了
+            if(memo[i] != null){
+                return memo[i];
+            }
+            if(set.contains(i)){
+                // 第i天要出行,则需计算第i天到第365天的最低花费
+                memo[i] = Math.min(Math.min(costs[0]+ dp(i+1),costs[1]+dp(i+7)),costs[2]+dp(i+30));
+            }else {
+                // 第i天不需要出行,则去计算第i+1天到第365天的最低花费
+                memo[i] = dp(i+1);
+            }
+            // 只有遍历完365天了才会逐层向前返回花费金额
+            return memo[i];
+        }
+    [3]复杂度分析:
+        (1)时间复杂度: O(W)
+            W=365是旅行计划中日期的最大值,我们需要计算W个解,而每个解最多需要查询3个其他的解,因此计算量为O(3?W)=O(W)
+        (2)空间复杂度: O(W)O(W)
+            们需要长度为 O(W)的数组来存储所有的解;
+```