jjzjj

algorithm - map 和动态规划更新

coder 2024-07-08 原文

给我的问题是

一个 child 正跑上 n 级楼梯， 一次可以跳 1 步、2 步或 3 步。 实现一种方法来计算 child 可以通过多少种可能的方式跑上楼梯。

http://play.golang.org/p/bpjIkMm9jH 

package main

import "fmt"

func CountWaysDP(n int, mm map[int]int) int {
  if n < 0 {
    return 0
  } else if n == 0 {
    return 1
  } else if mm[n] > -1 {
    return mm[n]
  } else {
    mm[n] = CountWaysDP(n-1, mm) +
      CountWaysDP(n-2, mm) +
      CountWaysDP(n-3, mm)
    return mm[n]
  }
}

func main() {
  mm := make(map[int]int)
  fmt.Println(CountWaysDP(10, mm), mm)
}

这只给了我 0 个 map[]。事实证明，动态递归在以下行结束:

else if mm[n] > -1

那我怎么用动态规划来解决这个问题呢？这与 Cracking the coding interview 中的解决方案完全相同......

最佳答案

你需要和0比较:

else if mm[n] > 0

当为不存在的键获取值时，map 返回 0。

您也可以使用数组/slice 代替映射，因为您知道映射键总是从 1 到 N

你也可以不用递归来解决这个问题:

package main

import "fmt"

func main() {
    n := 10
    mm := make([]int, n+1)
    mm[0] = 1
    for i := 1; i <= n; i++ {
        for k := 1; k <= 3; k++ {
            if i-k >= 0 {
                mm[i] += mm[i-k]
            }
        }
    }
    fmt.Println(mm)
    fmt.Println(mm[n])
}

关于algorithm - map 和动态规划更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22758328/

algorithmmapsectionmmCountWaysDPgo

有关algorithm - map 和动态规划更新的更多相关文章

  1. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  2. ruby-on-rails - 使用 rails 4 设计而不更新用户 - 2

    我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它​​不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。 最佳答案 如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数

  3. objective-c - 在设置 Cocoa Pods 和安装 Ruby 更新时出错 - 2

    我正在尝试为我的iOS应用程序设置cocoapods但是当我执行命令时:sudogemupdate--system我收到错误消息:当前已安装最新版本。中止。当我进入cocoapods的下一步时:sudogeminstallcocoapods我在MacOS10.8.5上遇到错误:ERROR:Errorinstallingcocoapods:cocoapods-trunkrequiresRubyversion>=2.0.0.我在MacOS10.9.4上尝试了同样的操作，但出现错误:ERROR:Couldnotfindavalidgem'cocoapods'(>=0),hereiswhy:U

  4. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  5. ruby-on-rails - Rails Associations 的更新方法是什么？ - 2

    这太简单了，太荒谬了，我在任何地方都找不到关于它的任何信息，包括API文档和Rails源代码:我有一个:belongs_to关联，我开始理解当您没有关联时您在Controller中调用的正常模型方法与您有关联时调用的方法略有不同。例如，我的关联在创建Controller操作时运行良好:@user=current_user@building=Building.new(params[:building])respond_todo|format|if@user.buildings.create(params[:building])#etcetera但我找不到关于更新如何工作的文档:@user

  6. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  7. ruby - 在 ruby​​ 中使用 .try 函数和 .map 函数 - 2

    我需要从json记录中获取一些值并像下面这样提取curr_json_doc['title']['genre'].map{|s|s['name']}.join(',')但对于某些记录，curr_json_doc['title']['genre']可以为空。所以我想对map和join()使用try函数。我试过如下curr_json_doc['title']['genre'].try(:map,{|s|s['name']}).try(:join,(','))但是没用。 最佳答案 你没有正确传递block。block被传递给参数括号外的方法

  8. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  9. ruby-on-rails - OSX Yosemite 更新破坏了 pow.cx - 2

    升级到OSXYosemite后，我现有的pow.cx安装不起作用。升级到最新的pow.cx无效。通过事件监视器重新启动它也没有成功。 最佳答案 卸载(!)并重新安装解决了这个问题。curlget.pow.cx/uninstall.sh|shcurlget.pow.cx|sh 关于ruby-on-rails-OSXYosemite更新破坏了pow.cx，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/q

  10. ruby - 将 Gitlab 从 9.3.7 更新到 9.3.8 安装 re2 时出错 - 2

    我们在Ubuntu14.04和Gitlab9.3.7上运行，运行良好。我们正在尝试更新到Gitlabv9.3.8的最新安全补丁，但它给我们这个错误:Gem::Ext::BuildError:ERROR:Failedtobuildgemnativeextension.currentdirectory:/home/git/gitlab/vendor/bundle/ruby/2.3.0/gems/re2-1.0.0/ext/re2/usr/local/bin/ruby-r./siteconf20170720-19622-15i0edf.rbextconf.rbcheckingformain(

随机推荐