当前位置:   article > 正文

让人费解的动态规划——最低票价_动态规划 始发站出发 终点站 票价最少

动态规划 始发站出发 终点站 票价最少

今天遇到的这道题,我知道要用动态规划,可就是想不出状态转移方程。看了题解,才明白,它倒序求得的。
题目链接如下:leetcode,最低票价

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

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

一张为期一天的通行证售价为 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,并完成了你计划的每一天旅行。
 

提示:
1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

  • 1
  • 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

题目耐心看,是可以看懂的。就是某几天你一定得坐火车, 有管一天的票,有管一周的票,还有管一月的票,怎么买,花费最少。

直接上代码,看了代码再细说。

以示例2为例来讲解代码逻辑
days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]

31天之后,都不必出行,那memo[32 ] 到memo[365]都是0,即不用花钱。
dp(31),买日票、周票、月票都可以,最小花费是买日票,即db(31) = 2
dp(30),同样是买日票得两张(30号和31号),周票、月票1张也可以,取最小花费,db(30) = 4;
			dp(30) 面临三种选择 
				dp(31) + 2 = 2 + 2 = 4 // 买张一日票,再加上31天之后的花费
				dp(37) + 7 = 0 +  7 =7 // 买张周票,再加上37天之后的
				dp(60) + 15 = 0 +  15 =15// 买张周票,再加上37天之后的
dp(29),不必出单,dp(29) = dp(30) = 4;
……  ……
dp(10) 面临三种选择 
				dp(11) + 2 = 4 + 2 = 6 // 买张一日票,再加上11天之后的花费
				dp(17) + 7 = 4 +  7 =11 // 买张周票,再加上17天之后的
				dp(40) + 15 = 0 +  15 =15// 买张周票,再加上40天之后的
……  …… 
从后往前,直到dp(1)就是本题答案
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
class Solution {
    int[] costs;
    Integer[] memo; // 计算过的,直接放数组里
    Set<Integer> dayset; // 记录哪些天要从火车
    public int mincostTickets(int[] days, int[] costs) {
        this.costs = costs;
        memo = new Integer[366];
        dayset = new HashSet();
        for(int day : days){
            dayset.add(day);
        }
        return dp(1);    
    }
    // 特别说明,dp(365) 返回的是 年尾这一天,坐车花的钱。
    // dp(364)返回的是 第364天至365天,坐车最小花费
    // dp(i) 返回的是 第i天,至第365天,坐车的最小花费
    // 所以,dp(1)就是要求的结果。
    private int dp(int i){
        if(i > 365) return 0;
        if(memo[i] != null) return memo[i];
        if(dayset.contains(i)){
            int a = dp(i + 1) + costs[0];
            int b = dp(i + 7) + costs[1];
            int c = dp(i + 30) + costs[2];
            memo[i] = getSmallest(a, b, c);
        }else{
            memo[i] = dp(i + 1);
        }
        return memo[i];
    }
    private int getSmallest(int a, int b, int c){
        return Math.min(a, Math.min(b,c));
    }
}
  • 1
  • 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

优化,上述dp(11)到dp(30) 值都相等,考虑在这上面优化。
这个不好理解,拿实例去套,慢慢就懂了。

class Solution {
    int[] costs;
    int[] days;
    Integer[] memo;
    int[] ways = new int[]{1, 7, 30};
    public int mincostTickets(int[] days, int[] costs) {
        this.costs = costs;
        this.days = days;
        memo = new Integer[days.length];
        return dp(0);    
    }
    private int dp(int i){
        if(i >= days.length) return 0;
        if(memo[i] != null) return memo[i];
        memo[i] = Integer.MAX_VALUE;
        int j = i;
        for(int k = 0; k < 3; k++){
            while(j < days.length && days[j] < days[i] + ways[k]){
                j++;
            }
            memo[i] = Math.min(memo[i], dp(j) + costs[k]);
        }       
        return memo[i];
    }
   
}
  • 1
  • 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

动态规划难,找不出动态转移方程的动态规划更难。

多练,多想,会有质变的一天。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/398215
推荐阅读
相关标签
  

闽ICP备14008679号