不同路径

weblog 239 0 0

leetcode62题(中等)【动态规划 dp】

原链接:https://leetcode-cn.com/problems/unique-paths/

题目描述

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例1

输入:m = 3, n = 7
输出:28

示例2

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

解题思路

动态规划,状态转移方程:

两种方案:

1.从开始节点到目标节点推算:dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

2.从目标节点到开始节点推算:dp[i][j]=dp[i+1][j]+dp[i][j+1];

代码

一般解法

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[n][m];
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(i==n-1||j==m-1){
                    dp[i][j]=1;
                }else{
                    dp[i][j]=dp[i+1][j]+dp[i][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

优化一下空间复杂度(状态压缩)

class Solution {
    public int uniquePaths(int m, int n) {
        int[] mm=new int[m];
        int[] nn=new int[n];
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(i==n-1||j==m-1){
                    mm[j]=nn[i]=1;
                }else{
                    mm[j]=nn[i]=mm[j]+nn[i];
                }
            }
        }
        return mm[0];
    }
}
猜你喜欢
框架 165 logback-spring.xmllogback-spring.xml?xmlversion="1.0"encoding="UTF-8"?configuration!--日志输出
official 346 。说明:叶子节点是指没有子节点的节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶子节点的为:1-2-5,1-3解题思递归得方式遍历二叉树(深度优先搜索),
数据结构与算法 8493 迷宫问题-寻找最短算法:广度优先搜索数据结构:队列,链表代码实现:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
spring/springmvc 4535 springboot动态设置@RequestMapping的url请求(从配置文件中获取或默认)controller层
weblog 9274 )。虽然它返回本身的细节,但是可以通过对算法的简单修改来重建。该算法的版本也可用于查找关系R的传递闭包,或(与Schulze投票系统相关)在加权图中所有顶点对之间的最宽。案例如有一个图(可以
算法基础 1694 ,当有类名,方法名匹配时也会出现。所以有时搜索的延时较长。二、idea安装RestfulToolkit插件该插件使用时完全匹配Controller控制层的url会出现干扰项,所以非常推荐。安装
linux系统 672 配置nginx代理二级域名访问项目二级域名a,访问项目aserver{listen80;server_namea.jiajiajia.com;location
前端(h5) 1696 functiongetQueryValue(key,href){ href=href||window.location.href; varmatch=href.match(newRegExp('[?&]'+key+'=([^&]*)')); returnmatch&&match[1]&&decodeURIComponent(match[1])||''
目录
祝愿神州十三飞行乘组平安归来