62. Unique Paths(中等，我自己解出的第一道 DP 题^^)

2022-10-17 08:02:22

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?

有个图来着，Markdown贴起来很麻烦．不贴了．

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

Note: $m$ and $n$ will be at most 100.

解题思路，没啥可说，用 dynamic programming.

步骤：

step 1: 看 https://mp.weixin.qq.com/s/0AgJmQNYAKzVOyigXiKQhA, 动态规划入门最好材料，没有之一！　10分钟看完，然后第二步．

step 2: 画图自己做这个题．^^

主要是先建模型，既，分析出：

状态转移公式，本题有３个状态转移公式，分别对应这i,j条件．具体参考最下方的代码（简单递归，当然无法执行，因为时间复杂度为 $O(2^n)$, 但能很好的展示了转移公式）;
最优子结构(分别对应各自的状态转移公式)；
边界，既F[0,0] = 1.

自己想法，自个代码^^:

$O(m*n)$ time, $O(n)$ extra space.

class Solution {

public:

    // 真正的DP求解

    // $O(m*n)$ time, $O(n)$ extra space.

    // 时间复杂度无法再小了，但空间复杂度还可以再小．

    // space complexity 最低可为 min(m, n);

    // 听说有 $O(1)$ 的空间复杂度？

    // 如果不用 DP, 可用 math 的方法，如下：

    // https://leetcode.com/problems/unique-paths/discuss/

    int uniquePaths(int m, int n) {

        if(m == 1 || n == 1) return 1;

        if(m < n) return uniquePaths(n, m);

        vector<int> temp(n - 1, 0);

        for(int i = 1; i < m; i++){

            for(int j = 1; j < n; j++){

                if(i == 1 && j == 1) temp[0] = 2;

                else if(i == 1 && j > 1) temp[j - 1] = 1 + temp[j - 2];

                else if(i > 1 && j == 1) temp[0] = temp[0] + 1;

                else if(i > 1 && j > 1) temp[j - 1] = temp[j - 1] + temp[j - 2];

            }

        }

        return temp[n - 2];

    }

};

下面是简单递归，但 time complexity $O(2^n)$, 太高了.

下面代码可清晰地展示出DP的三要素：

状态转移公式、最优子结构和边界．

class Solution {

public:

    // 方法一: 简单递归，但 time complexity $O(2^n)$, 太高了.

    int uniquePaths(int m, int n) {

        int i = m - 1, j = n - 1;

        if(i == 0 && j == 0) return 1;

        else if(i == 0 && j != 0) return uniquePaths(i, j - 1);

        else if(j == 0 && i != 0) return uniquePaths(i - 1, j);

        else if(j > 0 && i > 0) return uniquePaths(i, j - 1) + uniquePaths(i - 1, j);

    }

};

随机推荐

java泛型详解
http://www.cnblogs.com/lwbqqyumidi/p/3837629.html
document与window的区别
[window对象] 它是一个顶层对象,而不是另一个对象的属性,即浏览器的窗口. 属性 defaultStatus 缺省的状态条消息 document 当前显示的文档(该属性本身也是一个对象) fra ...
Workflow&lowbar;如何处理标准异常和自定义异常（案例）
2014-05-31 Created By BaoXinjian
调试exynos4412—ARM嵌入式Linux—LEDS/GPIO驱动之三
/** ****************************************************************************** * @author 暴走的小 ...
水平线、垂直线——axure线框图部件库介绍
1. 将水平线.垂直线拖动到axure页面编辑区域,如图: 2. 水平线.垂直线相关属性设置主要属性有.线条的颜色.粗细.线条的样式.箭头的样式来自:非原型不设计
搜索结果Refinement 行为总结之 multi-selection refinement
几乎所有的购物网站的搜索结果页面都会提供refinement (filtering) 给用户去过滤产品,以便能更快找到自己想要的产品.(做的都是国外的项目,不太清楚这个功能地道的中文名是什么.所以就暂 ...
与markdown的第一次接触
什么是markdown markdown是一种比html轻量级的标记语言. markdown的介绍与学习请参考:markdown认识与入门 CSDN Markdown博客视频教程知乎: 怎样引导新手 ...
zabbix--3&period;0--3
使用JMX监控jvm vim /usr/local/tomcat/bin/catalina.sh 添加如下内容 CATALINA_OPTS="$CATALINA_OPTS -Dcom ...
oracle提高查询效率的34个方面全解析
oracle提高查询效率的34个方面全解析在一个数据库中进行操作的时候,效率是很重要的,那么,如何提高oracle的查询效率呢?笔者将从以下几个方面进行详细解析: 1.选择最有效率的表名顺序(只 ...
web前端js 实现打印操作
转载来源:https://www.cnblogs.com/potatog/p/7412905.html 一.打印当前页面指定元素中的内容方式一:直接使用window.print(); (1)首先获得 ...

码农公寓

随机推荐

相关文章