草庐IT

leetcode 不同路径

Yeqqsy 2023-03-28 原文

初识动态规划，我对这个算法的理解是这样的：

1.找到初始值-原始解

2.在找到各种解与原始解的关系

3.通过循环得到答案

 

适用于动态规划的问题首先就是不同路径：

问题是给定一个M*N的地图从左上到右下角一共有多少种不同的方案（每次只能向右或者向下走一格）。

那么解决这个问题的关键在于你如何确定初始解与答案之间的联系。

首先我们可以确定地图的左边与上边都为1，因为只能往右或者下走。

例如从【0，0】走到【0，5】只能选择连续向右走五步，或者从【0，0】走到【5，0】只能选择连续向下走五步。

那么走到【1，1】有多少种走法？ 根据每次只能向下走一步或者向右走一步的特性，所以只能由【0，1】或者【1，0】到达【1，1】。也就是说【1，1】的走法就是【1，0】的走法加上【0，1】的走法。

其他类似，只需要知道左边与上面的格子的走法也就知道本格子的走法了。

 

这时我们设置一个二维数组DP【】【】，表示从【0，0】到【i，j】之间有多少种走法。

那么结合之前的分析可以得知DP【i】【j】 = DP【i - 1】【j】 + DP【i】【j - 1】

 

代码如下：

    public int uniquePaths(int m, int n) {
        int DP[][] = new int[m][n];
        for(int i = 0; i < m; i++)
            DP[i][0] = 1;
        for(int i = 0; i < n; i++)
            DP[0][i] = 1;
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                DP[i][j] = DP[i - 1][j] + DP[i][j - 1];

        return DP[m - 1][n - 1];
    }

 

leetcode不同spancolorstyle算法与数据结构

有关leetcode 不同路径的更多相关文章

  1. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

    如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. java - 为什么 ruby​​ modulo 与 java/other lang 不同？ - 2

    我基本上来自Java背景并且努力理解Ruby中的模运算。(5%3)(-5%3)(5%-3)(-5%-3)Java中的上述操作产生，2个-22个-2但在Ruby中，相同的表达式会产生21个-1-2.Ruby在逻辑上有多擅长这个？模块操作在Ruby中是如何实现的？如果将同一个操作定义为一个web服务，两个服务如何匹配逻辑。 最佳答案 在Java中，模运算的结果与被除数的符号相同。在Ruby中，它与除数的符号相同。remainder()在Ruby中与被除数的符号相同。您可能还想引用modulooperation.

  4. ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  5. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  6. ruby-on-rails - 如何用不同的用户运行nginx主进程 - 2

    A/ctohttp://wiki.nginx.org/CoreModule#usermaster进程曾经以root用户运行，是否可以以不同的用户运行nginxmaster进程？ 最佳答案 只需以非root身份运行init脚本(即/etc/init.d/nginxstart)，就可以用不同的用户运行nginxmaster进程。如果这真的是你想要做的，你将需要确保日志和pid目录(通常是/var/log/nginx&/var/run/nginx.pid)对该用户是可写的，并且您所有的listen调用都是针对大于1024的端口(因为绑定(

  7. ruby-on-rails - 如何播种图像的路径？ - 2

    Organization和Image具有一对一的关系。Image有一个名为filename的列，它存储文件的路径。我在Assets管道中包含这样一个文件:app/assets/other/image.jpg。播种时如何包含此文件的路径？我已经在我的种子文件中尝试过:@organization=...@organization.image.create!(filename:File.open('app/assets/other/image.jpg'))#Ialsotried:#@organization.image.create!(filename:'app/assets/other/i

  8. ruby - 从 sinatra 中的 before do block 返回不同的值 - 2

    有没有办法在sinatra的beforedoblock中停止执行并返回不同的值？beforedo#codeishere#Iwouldliketo'return"Message"'#Iwouldlike"/home"tonotgetcalled.end//restofthecodeget'/home'doend 最佳答案 beforedohalt401,{'Content-Type'=>'text/plain'},'Message!'end如果你愿意，你可以只指定状态，这里有状态、标题和正文的例子

  9. ruby-on-rails - Sunspot:如何对具有不同值的多个字段进行全文查询？ - 2

    我想用sunspot重现以下原始solr查询q=exact_term_text:fooORterm_textv:foo*ORalternate_text:bar*但我无法通过标准的太阳黑子界面理解这是否可能以及如何实现，因为看起来:fulltext方法似乎不接受多个文本/搜索字段参数我不知道将什么参数作为第一个参数传递给fulltext，就好像我通过了"foo"或"bar"结果不匹配如果我传递一个空参数，我得到一个q=*:*范围过滤器(例如with(:term).starting_with('foo*')(顾名思义)作为过滤器查询应用，因此不参与评分。似乎可以手动编写字符串(或者可能使

  10. ruby - 拆分字符串并分配给不同的变量 - 2

    我从ui中得到日期范围为-approved_between"=>"2013-03-17-2013-03-18"我需要拆分此approved_start_date="2013-03-17"和approved_end_date="2013-03-18"...我希望使用它在mysql中查询，因为mysql中的日期格式是created_at:2012-07-2810:35:01.我正在做的是:approved=approved_between.split("")approved_start_date=approved[0]approved_end_date=approved[2]很确定这不是处

随机推荐