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

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);

    }

};

随机推荐

loadrunner生成随机身份证和银行卡号
生成银行卡号码: Action() { char card[19] = {'6','2','2','7','0','0','0','0','0','0','0','0','0','0','0','0' ...
用sass画蜗牛
一.sass的好处用css画图也算是简单的实战吧,虽然用到的东西还比较少..用过之后,发现sass主要有以下优势: 可维护性.最重要的一点,可维护性的很大一部分来自变量嗯,最简单的例子,画图总要有 ...
JVM值内存垃圾回收监控之jstat
如何判断JVM垃圾回收是否正常?一般的top指令基本上满足不了这样的需求,因为top主要监控的是总体的系统资源,很难定位到java应用程序. Jstat是JDK自带的一个轻量级小工具.全称“Java ...
安装Laravel之坎坷记述
写这篇文章记录以及分享我安装Laravel框架的一些经验过程如下: 1.按照官方的描述,第一步是先安装composer来管理依赖=>composer下载传送门下载之后点击安装,按照提示它需要 ...
GUI自绘&lowbar;其中左边树状菜单控件风格灵感来源于城市博物馆的壁灯效果。
GUI DEMO 下面都是去年做的演示DEMO,到目前为止,除了专门做界面库的公司,暂时还没有看到别人做的效果比我这个更好的. 下图在第一张图中有个错误,看出来了没有呢? 就是项目核算那儿,不应该是B ...
由merge into引起的序列跳号
最近生产库反应出一个问题,某张表的主键ID并没有按照原计划的期望增加,而是间歇性跳号,每次跳2万多,经过研究发现是某个同步过程的merge into引起的,具体语句如下 merge into t_if ...
jQuery中下拉select、复选checkbox、单选radio的操作代码
//select $("#Icon") //对象 $("#Icon").val() //取值 $("#Icon").val("fa ...
62&period;纯 CSS 创作一只蒸锅（感觉不好看呀）
原文地址:https://segmentfault.com/a/1190000015389338 HTML code: <!-- steamer: 蒸锅: lid: 盖子: pot: 锅 --& ...
从零开始学习Vue(四)
这里引入一个概念SPA(single Page Application), 接着上次的例子,我们在页面底部做了一个Tab的菜单,点击不同的按钮应该是显示不同的内容. 按传统的MVC的思维,我要在Con ...
1&colon;(0or1)
public class User { public int ID { get; set; } public string UserName { get; set; } ...

秒客网

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

随机推荐

相关文章