1553. Minimum Number of Days to Eat N Oranges

题目信息

题号:

1553

难度:

Hard

主题:

动态规划、记忆化搜索、数学

原题:

LeetCode 1553

重点:

每天可吃一个;数量被二整除时可吃一半,被三整除时可吃三分之二,求吃完的最少天数

题目重述

初始有 n 个橙子。每天必须选择一种合法操作:吃掉一个橙子;若当前数量能被 2 整除,吃掉其中一半;若能被 3 整除,吃掉其中三分之二。

每种操作都消耗一天。请返回吃完所有橙子所需的最少天数。

1 <= n <= 2 * 10^9。

自建示例

先调整到可整除数量可以减少总天数:

输入:n = 10
输出:4
解释:10 -> 9 -> 3 -> 1 -> 0,分别吃 1、6、2、1 个橙子。

只有一个橙子时需要一天:

输入:n = 1
输出:1
解释:执行一次吃掉一个橙子的操作。