最低票价
题目
思路
一天天过一遍，每到一天往前看一下，选出三种情况最小值。
代码
class Solution {
public:
int mincostTickets(vector
<int>& days
, vector
<int>& costs
) {
int n
=days
[days
.size()-1];
vector
<int> dp(n
+1,0);
for(int i
=0;i
<days
.size();i
++)
dp
[days
[i
]]=1;
int c1
,c2
,c3
;
for(int i
=1;i
<=n
;i
++)
{
if(!dp
[i
]) dp
[i
]=dp
[i
-1];
else
{
c1
=dp
[i
-1]+costs
[0];
if(i
>=7) c2
=dp
[i
-7]+costs
[1];
else c2
=costs
[1];
if(i
>=30) c3
=dp
[i
-30]+costs
[2];
else c3
=costs
[2];
dp
[i
]=min(c1
,min(c2
,c3
));
}
}
return dp
[n
];
}
};
