专栏首页算法修养LeetCode 1553. Minimum Number of Days to Eat N Oranges

LeetCode 1553. Minimum Number of Days to Eat N Oranges

题目

题意:一堆橘子,要么吃一个,如果橘子数量能被2整除就可以吃一半,如果橘子数量能被3整除就可以吃三分之二,请问最少几次能吃完?

题解:橘子的个数是n,按照贪心的思想,肯定是吃一半或者吃三分之二划算。因此每一步,都有两种选择,要么一个一给吃,吃到能被2整除,然后吃掉一半。要么一个一个吃,吃到能被3整除,然后吃掉三分之二。取二者的最小者。 所以,就是一个递归DP的过程,还要记得记录状态,以节约时间。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode笔记:Weekly Contest 202 比赛记录

    我们考察达到最终结果时的状态,由于原始态的向量为:[1,3,5,...,2n−1],故达到平衡态时,所有的元素变为:[n,n,n,...,n],因此,每一个元素...

    codename_cys
  • 【Oracle】-【AWR/Stackpack】-AWR(Stackpack)执行权限

    Oracle 9i执行Stackpack(10g是AWR),当前是一个普通账户,没有DBA权限。

    bisal
  • LeetCode Weekly Contest 32解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • CodeForces 732B Cormen — The Best Friend Of a Man

    B. Cormen — The Best Friend Of a Man time limit per test 1 second memory lim...

    ShenduCC
  • CodeForces 732D Exams

    D. Exams time limit per test 1 second memory limit per test 256 megabytes ...

    ShenduCC
  • Codeforces 839A Arya and Bran【暴力】

    A. Arya and Bran time limit per test:1 second memory limit per test:256 megabyte...

    Angel_Kitty
  • Minimum Cost For Tickets

    In a country popular for train travel, you have planned some train travelling on...

    卡尔曼和玻尔兹曼谁曼
  • CF--思维练习--CodeForces - 216C - Hiring Staff (思维+模拟)

    ACM思维题训练集合 A new Berland businessman Vitaly is going to open a household applia...

    风骨散人Chiam
  • ZOJ 3498 Javabeans

    Javabeans Time Limit: 2 Seconds Memory Limit: 65536 KB Javabeans are de...

    ShenduCC
  • 2018-2019 ICPC, NEERC, Southern Subregional Contest D. Garbage Disposal

    Enough is enough. Too many times it happened that Vasya forgot to dispose of gar...

    glm233
  • CF思维联系– CodeForces - 991C Candies(二分)

    After passing a test, Vasya got himself a box of n candies. He decided to eat an...

    风骨散人Chiam
  • Codeforces 789A Anastasia and pebbles(数学,思维题)

    A. Anastasia and pebbles time limit per test:1 second memory limit per test:256 ...

    Angel_Kitty
  • LightOJ 1203--Guarding Bananas(二维凸包+内角计算)

    Once there was a lazy monkey in a forest. But he loved banana too much. One day ...

    Enterprise_
  • LeetCode Weekly Contest 38解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode Weekly Contest 43解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 一行代码修改Linux机器密码和Samba服务密码

    当我们需要用命令代替我们往Linux窗口输入东西时,可以考虑使用Linux文件描述符里的标准输入,而passwd、smbpasswd命令均有自己对应的标准输入参...

    GH
  • 关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements

    关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements 题目 Given a non-e...

    WZEARW
  • Oracle-AWR管理包DBMS_WORKLOAD_REPOSITORY.MODIFY_SNAPSHOT_SETTINGS

    Overview of the Automatic Workload Repository

    小小工匠
  • POJ 3273 Monthly Expense

    Monthly Expense Time Limit: 2000MS Memory Limit: 65536K Total Submissions: ...

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券