LeetCode 1553. 吃掉 N 个橘子的最少天数（dp）

题意：

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。请你返回吃掉所有 n 个橘子的最少天数。数据范围:
1 <= n <= 2*10^9

解法：

令d[i]表示i个橘子需要的最少天数,
因为橘子的数量只能递减,因此状态可以转化为拓扑图,
但是因为有-1操作,所以总状态数是O(n)的,但是当能进行/2或/3操作时,一定不会使用-1,因此-1操作使用的次数是有限的,
-1操作要用到的地方:
1:当前是奇数,-1变成偶数,然后进行操作/2.
2:当前%3!=0,利用-1操作变成%3=0,然后进行操作/3.O(n)的状态中,每个状态之间转移的代价是1,
我们可以将-1操作转化为边权,把图变成只有O(log)个状态的,边权>=1的拓扑图.
每个状态为n/(2^x)/(3^y),
dp即可.转移方程:
d[i]=min(d[i/2]+i%2+1,d[i/3]+i%3+1).ps:
既然已经将状态图是O(log)个点的拓扑图,那么最短路也可以做.

code：

class Solution {
public:map<int,int>mp;int dfs(int i){if(i==0)return 0;if(i==1)return 1;if(mp.count(i))return mp[i];return mp[i]=min(dfs(i/2)+i%2+1,dfs(i/3)+i%3+1);}int minDays(int n) {mp.clear();return dfs(n);}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！