草庐IT

day45|● 70. 爬楼梯 （进阶）● 322. 零钱兑换 ● 279.完全平方数

星轨道交 2023-04-09 原文

70. 爬楼梯（完全背包）

1.代码

class Solution {
public:
    int climbStairs(int n) {
    vector<int>nums;
    vector<int>f(n + 1);
     f[0] = 1;
     for (int i = 0; i <= n; i++) {
         for (int j = 1; j <= 2; j++) {
             if (i >= j) f[i] += f[i - j];
         } 
     }
     return f[n];
    }
};

2.递归五部曲

1.确定dp数组和其下标的含义

题目所求是爬到楼梯顶的方案数，f[i]就是爬到i层的方案数。f[n]就是爬到楼顶的方案数

2.确定递推公式

题目所求是方案数，如f[i]，方案数就是所有可以到达i的方案数相加，比如可以走1步和2步，f[i] = f[i - 1] + f[i - 2] + f[i - 3] +......，所以遍历到这个物品时候，就可以加入到达这个背包的方案数了

f[i] += f[i - nums[j]]

3.初始化

由递推公式可知，没有可以叠加的值，所以必须初始化，f[0]=1

4.确定遍历顺序

因为是求排列数，说明顺序不同也是一种方案，所以需要第一层for循环遍历背包，让背包来筛选物品，第二层是遍历物品，就是遍历台阶，因为台阶只有两种，完全可以用变量来代替

5.举例说明dp公式

距离前面几个代入dp公式，看一下正确不正确

322. 零钱兑换

1.代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
         vector<int>f(amount + 1, INT_MAX);
         f[0] = 0;
         for (int i  = 0; i < coins.size(); i++) {
             for (int j = coins[i]; j <= amount; j++) {
                if (f[j - coins[i]] < INT_MAX - 1) f[j] = min(f[j], f[j - coins[i]] + 1);
             }
         }
         if (f[amount] == INT_MAX) return -1;
         return f[amount];
    }  
};

2.递归五部曲

1.确定dp数组和下标的含义

题目是凑成总金额所需的 最少的硬币个数，所以dp[j]就是求出凑成钱数j的最小硬币个数，

2.确定递推公式

每次凑足总金额j - coins[i]最小个数时f[j - coins[i]],那么只要加上这个硬币就可以得到dp[i],所以求f[j - coins[i]]+1的最小值就是dp[j]的结果，相当于遍历所有类型的硬币，加上这个硬币的最小硬币个数

dp[j] = min(dp[j], dp[j - nums[i]] + 1)

3.初始化

一开始全部都设置为int的最大值，因为是求最小值，第一个值不能为最大值，因为这样不符合公式的推导，f[0]=0，符合凑出0元，需要的硬币数

4.遍历顺序

第一层遍历物品，第二层顺序遍历背包，为了重复选择硬币。因为是求组合数所以是这样的

5.举例前几个证明dp数组

279. 完全平方数

1.代码

class Solution {
public:
    int numSquares(int n) {
        vector<int>f(n + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i*i <= n; i++) {
            for (int j = i*i; j <= n; j++) {
                f[j] = min(f[j], f[j - i*i] + 1);
            }
        }
        return f[n];
    }
};

2.动规五部曲

思路：题目是求平方数相加等于目标数的平方数的最小数量

比如目标数为13，最少平方数相加为4+9

所以我们可以转化一个问题，在sqrt(taeget)的这些数的平方数相当于物品，选择这些物品可以到达总体积的最少物品数，因为可以重复选，所以可以转化成完全背包

1.确定dp数组和其下标的含义

dp[j]就是合成j的最小平方数

2.确定递推公式

                f[j] = min(f[j], f[j - i*i] + 1);

与每一个可以选择的平方数比较，选择最小的一个

3.初始化

和第二题一样

4.遍历顺序

第一层是背包大小，第二层是平方数，

5.模拟

进阶零钱ampltgt

有关day45|● 70. 爬楼梯 （进阶）● 322. 零钱兑换 ● 279.完全平方数的更多相关文章

  1. ruby-on-rails - rails : Find tasks that were created on a certain day? - 2

    我有一个任务列表(名称、starts_at)，我试图在每日View中显示它们(就像iCal)。deftodays_tasks(day)Task.find(:all,:conditions=>["starts_atbetween?and?",day.beginning,day.ending]end我不知道如何将Time.now(例如“2009-04-1210:00:00”)动态转换为一天的开始(和结束)，以便进行比较。 最佳答案 deftodays_tasks(now=Time.now)Task.find(:all,:conditio

  2. 什么是0day漏洞？如何预防0day攻击？ - 2

    什么是0day漏洞？0day漏洞，是指已经被发现，但是还未被公开，同时官方还没有相关补丁的漏洞；通俗的讲，就是除了黑客，没人知道他的存在，其往往具有很大的突发性、破坏性、致命性。0day漏洞之所以称为0day，正是因为其补丁永远晚于攻击。所以攻击者利用0day漏洞攻击的成功率极高，往往可以达到目的并全身而退，而防守方却一无所知，只有在漏洞公布之后，才后知后觉，却为时已晚。“后知后觉、反应迟钝”就是当前安全防护面对0day攻击的真实写照！为了方便大家理解，中科三方为大家梳理当前安全防护模式下，一个漏洞从发现到解决的三个时间节点：T0：此时漏洞即0day漏洞，是已经被发现，还未被公开，官方还没有相

  3. ruby - Rails 比较 date.end_of_day.to_datetime 和 date.to_datetime.end_of_day 返回的日期对象值时返回 false - 2

    ruby1.9.3dev(2011-09-23修订版33323)[i686-linux]轨道3.0.20最近为什么在与DateTimeonRails相关的RSpecs项目上工作我发现在给定日期以下语句发出的值date.end_of_day.to_datetime和date.to_datetime.end_of_day虽然它们表示相同的日期时间，但比较时返回false。为了确认这一点，我打开了Rails控制台并尝试了以下操作1.9.3dev:053>monday=Time.now.monday=>2013-02-2500:00:00+05301.9.3dev:054>monday.cla

  4. ruby - 如何修复此错误 : kernel_require. rb :45:in `require' : cannot load such file? - 2

    我有以下文件结构:执行.rb图书馆我的类(class).rb在execute.rb我有下面的代码:#!/usr/bin/rubyrequire'lib/my_class'my_object=MyClass.newmy_object.some_method这是my_class.rb的代码:classMyClassdefsome_methodputs'OK'endend所以，我尝试运行execute.rb:rubyexecute.rb但是我收到这个错误:/home/vagrant/.rvm/rubies/ruby-2.0.0-p195/lib/ruby/site_ruby/2.0.0/ru

  5. 【第37天】斐波那契数列与爬楼梯 | 迭代的鼻祖，递推与记忆化 - 2

    本文已收录于专栏?《Java入门一百例》?学习指引序、专栏前言一、递推与记忆化二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题1】1、题目描述2.解题思路3、模板代码4、代码解析5、原题链接三、推荐专栏四、课后习题序、专栏前言  本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习

  6. Ruby，从 Date.day_fraction_to_time 获取小时、秒和时间 - 2

    我找到了这个方法here.start=DateTime.nowsleep15stop=DateTime.now#minutesputs((stop-start)*24*60).to_ihours,minutes,seconds,frac=Date.day_fraction_to_time(stop-start)我有以下错误:`':privatemethod`day_fraction_to_time'calledforDate:Class(NoMethodError)我检查了/usr/lib/ruby/1.9.1/date.rb并找到了它:defday_fraction_to_time(

  7. ruby - 尝试使用 Selenium Webdriver v3.70 最大化浏览器窗口时出现 Ruby "KeyError: key not found: 102"错误 - 2

    我最近将我的SeleniumWebdriver版本升级到3.70，当我尝试最大化浏览器窗口时，出现此错误:KeyError:keynotfound:102预先最大化窗口(在以前的版本中)似乎工作得非常好，我不确定这是否只是巧合，因为它不是标准类型的Selenium错误。这是我的代码:profile=Selenium::WebDriver::Chrome::Profile.new$driver=Selenium::WebDriver.for:chrome,:profile=>profile$driver.manage.window.maximize还有其他人遇到这个问题吗？另外值得注意的

  8. Ruby strftime : Day without leading zero, %e 不工作 - 2

    我正在尝试用没有前导零的日期来格式化日期使用%d它工作正常，但前导零date_time.strftime("%d/%m/%y")result:04/01/11我搜索了一下，发现我应该使用%e而不是%d，但是执行以下操作会得到一个空字符串。date_time.strftime("%e/%m/%y")result:这跟Ruby的版本有关系吗？我在Windows机器上使用v1.8.7。更重要的是，是否有另一种方法可以在没有前导零的情况下完成一天(比gsub更方便)？ 最佳答案 如果你想删除月份或日期的前导零，只需在格式前添加一个减号，如下

  9. ruby-on-rails - Rails : Date. 今天 - 1.day - 2

    使用rails控制台，我只是被这个咬住了:假设今天是12月11日。Date.today-1.day#December10(nospaces)Date.today-1.day#December10(aspaceonbothsidesoftheminussign)Date.today-1.day#December11whaaaat?Date.today-5.days#Stilldecember11!有人能解释一下这是怎么回事吗？我有点担心这在代码中很容易被遗漏。关于如何对此进行编码还有其他建议吗？ 最佳答案 您看到的差异是由ruby​​

  10. ruby-on-rails - Ruby - 无法在 45 秒内绑定(bind)到锁定端口 7054 (Selenium::WebDriver::Error::WebDriverError) - 2

    我最近开始在尝试运行任何Cucumber测试时看到此错误消息。我做了一些研究并发现了其他一些类似的此错误实例，但其中大多数是与浏览器相关的问题。我在此输出中没有看到任何特定于浏览器的错误消息:unabletobindtolockingport7054within45seconds(Selenium::WebDriver::Error::WebDriverError)我看到这里发布的另一个问题已得到解答(Aseleniumwebdriverexception)，但该解决方案对我不起作用。运行“lsof-iTCP:7054”不会产生任何输出。以防万一有人提出这个建议，我已经多次重启我的机器

随机推荐