Problem: 1553. 吃掉 N 個橘子的最少天數

題目

使得 n 變成0的操作有三種方式 ：

• 吃掉一個橘子。
• 如果剩余橘子數 n 能被 2 整除，那么你可以吃掉 n/2 個橘子。
• 如果剩余橘子數 n 能被 3 整除，那么你可以吃掉 2*(n/3) 個橘子。

思路

如果我們每天吃一個橘子（每次是操作1），那么從n到0要經過n天，所以最壞的情況下就是n。 要想保證天數最少，最好每天吃的最多。最暴力的方法就是

class Solution {
public:// 記錄吃掉n 個橘子的最少天數unordered_map<int,int> memo ; int minDays(int n) {if(n == 1 ) {memo[n] = 1 ; return 1 ; }if(memo.count(n)) {return memo[n] ; }if(n%2 == 0 && n%3 ==0 ){memo[n] = min( minDays(n/2), minDays(n/3)) +1  ;memo[n] = min(memo[n] ,minDays(n-1)) ; return memo[n] ; }else if(n %2 == 0 && n%3 !=0 ){return memo[n] = min (minDays(n/2) , minDays(n-1) ) +1 ; ; }else if( n%3 ==0 && n%2 !=0) {return memo[n] = min( minDays(n/3) , minDays(n-1) )+1  ; }else{return memo[n] = minDays(n-1) +1 ;}return memo[n] ; }
};

但是顯然是導致棧溢出

優化一下

我們肯定是希望吃掉一個橘子這樣的操作盡可能少（貪心）。優先選擇操作2和3.

• 假設，我們對n 先進行k次操作，然后再進行操作2，那么橘子的數量就從n 變成了(n-k)/2 。 一共操作了 k+1次；如果我們先將n變成靠近2的倍數的那個數 $n_t(n_t<n$ )，然后再執行操作1. 假設$k_0$ 是 $|n?n_t|$, $k_0$是模2的余數,那么我們只需要執行 $k_0$ 次的操作1(靠近2的倍數) ，然后執行1次操作2 和 $(k?k_0)$次的操作1，即eq.1
  $$\frac{(n?k_0)}{2}?\frac{(k?k_0)}{2}=\frac{(n?k)}{2}（1）$$
  一共執行了 $k_0+1+\frac{(k?k_0)}{2}$ 次 小于 $k+1$次。
  同理操作3 也是可以這樣處理 。

Code

class Solution {
public:unordered_map<int,int> memo; int minDays(int n) {if(n <=1 ) return n ; if(memo.count(n) ) {return memo[n] ; }// 通過操作1減少到靠近2和3的倍數int k0_2 =  n%2 ; int k0_3 =  n%3 ; return memo[n] = min(k0_2 +minDays(n/2) , k0_3 +minDays(n/3) ) +1; }};