LeetCode <dp>62&63.Unique Paths I&II

62.Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

题目大意:问有多少种走法

解法一:

采用递归形式的解法,这是一个典型的动态规划问题,采用记忆化搜索法。

    public int uniquePaths(int m, int n) {
       int [][] mem = new int[m+1][n+1];
       return  helper(m,n,mem);
    }
    public int helper(int m, int n,int [][] mem){
        if (m == 1|| n ==1){
            return 1;
        }
        if (mem[m][n] ==0){
            mem[m][n] = helper(m-1,n,mem)+helper(m,n-1,mem);
        }
       return mem [m][n];
    }

解法二:

非递归形式的解法。

    public int uniquePaths(int m, int n) {
        int [][] mem = new int[m][n];
        for (int i = 0;i<m;i++){
            for (int j = 0;j<n;j++){
                if (i==0||j==0){
                    mem[i][j] = 1;
                    continue;
                }
                if (mem[i][j] == 0) {
                    mem[i][j] = mem[i][j-1]+mem[i-1][j];
                }
            }
        }
        return mem[m-1][n-1];
    }

解法三:

解法一与解法二没有本质的区别,就是递归与非递归的区别,解法三采用的是一维的滚动数组,压缩存储中间量的空间。

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

63.Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

题目大意:矩阵中1代表障碍物,问有多少中走法。

解法:

思路:采用的一维空间的数组解决。

    * obstacleGrid =  0,0,0
     *                 0,1,0
     *                 0,0,0
     *    index of dp 0,1,2,3
     *   first time   0,1,1,1
     *   sec   time   0,1,0,1
     *   third time   0,1,1,2
     *
     *   ******************
     * obstacleGrid =  0,0,0
     *                 0,0,0
     *                 0,0,0
     *    index of dp 0,1,2,3
     *   first time   0,1,1,1
     *   sec   time   0,1,2,3
     *   third time   0,1,3,6

解法如下:

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int [] dp = new int[n+1];
    dp[1]=1;
    for (int i = 0;i<m;i++){
        for (int j = 1;j<=n;j++){
            if (obstacleGrid[i][j-1] ==1){
                dp[j] = 0;
            }else {
                dp[j] += dp[j-1];
            }
        }
    }
    return dp[n];
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

[c#]Webservice中如何实现方法重载(overload)以及如何传送不能序列化的对象作参数

1。Webservice中的方法重载问题 (1)在要重载的WebMethod上打个MessageName标签 比如: [WebMethod(Message...

19710
来自专栏计算机视觉与深度学习基础

Leetcode 213 House Robber II

Note: This is an extension of House Robber. After robbing those houses on that...

2098
来自专栏码匠的流水账

bloomfilter的简单实现

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,可以用于检索一个元素是否在一个集合中。

741
来自专栏FD的专栏

编辑器背后的数据结构

大约刚上大二的时候,想做一个编辑器控件。不是一个用Scintilla套上外壳的编辑器,而是一个能被套上外壳的控件。当然它最后也成为了我众多流产了的练手项目中的一...

1843
来自专栏Android知识点总结

看得见的数据结构Android版之双链表篇

741
来自专栏码匠的流水账

聊聊storm的AssignmentDistributionService

本文主要研究一下storm的AssignmentDistributionService

1521
来自专栏码匠的流水账

聊聊storm的window trigger

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/windowing/WindowTridentPr...

1310
来自专栏小樱的经验随笔

Codeforces 768B Code For 1

B. Code For 1 time limit per test:2 seconds memory limit per test:256 megabytes ...

3768
来自专栏码匠的流水账

聊聊storm的maxSpoutPending

storm-2.0.0/storm-client/src/jvm/org/apache/storm/Config.java

2425
来自专栏Seebug漏洞平台

Pwnhub之奇妙的巨蟒 Writeup

本周的Pwnhub延迟到了周一,所以周一中午就看了下这题,是一道Python 的pyc逆向题,思路到挺简单的,但是很花精力

60210

扫码关注云+社区

领取腾讯云代金券