1553. Minimum Number of Days to Eat N Oranges¶
题目信息¶
- 题号:
1553
- 难度:
Hard
- 主题:
动态规划、记忆化搜索、数学
- 原题:
- 重点:
每天可吃一个;数量被二整除时可吃一半,被三整除时可吃三分之二,求吃完的最少天数
题目重述¶
初始有 n 个橙子。每天必须选择一种合法操作:吃掉一个橙子;若当前数量能被 2 整除,吃掉其中一半;若能被 3 整除,吃掉其中三分之二。
每种操作都消耗一天。请返回吃完所有橙子所需的最少天数。
1 <= n <= 2 * 10^9。
自建示例¶
先调整到可整除数量可以减少总天数:
输入:n = 10
输出:4
解释:10 -> 9 -> 3 -> 1 -> 0,分别吃 1、6、2、1 个橙子。
只有一个橙子时需要一天:
输入:n = 1
输出:1
解释:执行一次吃掉一个橙子的操作。