leetcode 983.最低票价

题目链接：https://leetcode-cn.com/problems/minimum-cost-for-tickets/

思路：记忆化搜索

1. 倒着递推，dp[i]表示第i天到最后一天需要的钱。
2. 两种状态：
   1. 第i天不需要旅行，第i天的钱数和第i+1天相同，即dp[i]=dp[i+1]
   2. 第i天需要旅行，那么这天买票的方案有三种。这就是dp无后效性的精妙之处，考虑第i天的情况的时候，根本不用考虑第i天之前的，把每一天当作第一天来过。
3. T了竟然，原因是dp的初始值设的太小了，某个dp值保持初始值，后面更新的时候，都是初始值了，这样的话没法直接返回dp[k+access[i]],每次都要递归跑到头。

class Solution {
public:
    int bitmap[366];
    int access[3]={1,7,30};
    int dp[500];
    int ddp(int k,vector<int>& days, vector<int>& costs)
    {
        if(k>365)
        {
            return 0;
        }
        if(dp[k]!=400000)
        {
            return dp[k];
        }
        if(bitmap[k]==1)
        {
            for(int i=0;i<3;i++)
            {
                dp[k]=min(dp[k],costs[i]+ddp(k+access[i],days,costs));
            }
        }
        if(bitmap[k]==0)
        {
            dp[k]=ddp(k+1,days,costs);
        }
        return dp[k];
    }
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        for(int i=0;i<400;i++)
        {
            dp[i]=400000;
        }
        memset(bitmap,0,sizeof(bitmap));
        for(int i=0;i<days.size();i++)
        {
            bitmap[days[i]]=1;
        }
        return ddp(1,days,costs);
    }
};

leetcode 983.最低票价

原文：https://www.cnblogs.com/hang-shao/p/12839675.html