docs/Algorithm/Leetcode/Python/062._unique_paths.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 062.unique_paths 不同路径\n",
    "\n",
    "### 难度：Medium\n",
    "\n",
    "## 刷题内容\n",
    "\n",
    "> 原题链接\n",
    "\n",
    " - 中文：https://leetcode-cn.com/problems/unique-paths\n",
    " - 英文：https://leetcode.com/problems/unique-paths\n",
    " \n",
    "> 内容描述\n",
    "\n",
    "```\n",
    "一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。\n",
    "\n",
    "机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。\n",
    "\n",
    "问总共有多少条不同的路径？\n",
    "\n",
    "说明：m 和 n 的值均不超过 100。\n",
    "\n",
    "示例 1:\n",
    "输入: m = 3, n = 2\n",
    "输出: 3\n",
    "解释:\n",
    "从左上角开始，总共有 3 条路径可以到达右下角。\n",
    "1. 向右 -> 向右 -> 向下\n",
    "2. 向右 -> 向下 -> 向右\n",
    "3. 向下 -> 向右 -> 向右\n",
    "\n",
    "示例 2:\n",
    "输入: m = 7, n = 3\n",
    "输出: 28\n",
    "\n",
    "例如，下图是一个3 x 7 的网格。有多少可能的路径？\n",
    "```\n",
    "\n",
    "![](img/robot_maze.png)\n",
    "\n",
    "## 解决方案\n",
    "\n",
    "> 思路 1\n",
    "\n",
    "数学思路。\n",
    "\n",
    "本质上，这道题就是排列组合，一共走 m + n - 步，其中 m - 1 步是向右边走，所以不就是从 m + n - 2 中选择 m-1 个的问题，阶乘问题，so easy ！妈妈再也不用担心我的学习！！！这个方法 beats 99.97% 。\n",
    "\n",
    "补充一下，math 模块中自带 factorial 函数，只要 import math 之后调用即可。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28.0\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def uniquePaths(self, m, n):\n",
    "        \"\"\"\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def factorial(num):\n",
    "            res = 1\n",
    "            for i in range(1, num+1):\n",
    "                res *= i\n",
    "            return res\n",
    "        return factorial(m+n-2)/factorial(n-1)/factorial(m-1)\n",
    "    \n",
    "s = Solution()\n",
    "print(s.uniquePaths(7,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "> 思路 2\n",
    "\n",
    "片刻大佬 想到的这个思想，真的棒！\n",
    "\n",
    "| | | |\n",
    "| - | - | - |\n",
    "| 1 | 1 | 1 |\n",
    "| 1 | 2 | 3 |\n",
    "| 1 | 3 | 6 |\n",
    "| 1 | 4 | 10 |\n",
    "| 1 | 5 | 15 |\n",
    "| 1 | 6 | 21 |\n",
    "| 1 | 7 | 28 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def uniquePaths(self, m, n):\n",
    "        \"\"\"\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if m < 1 or n < 1:\n",
    "            return 0\n",
    "        dp = [0] *n\n",
    "        dp[0] = 1    \n",
    "        for i in range(0,m):\n",
    "            for j in range(1,n):\n",
    "                dp[j] += dp[j-1]\n",
    "        return dp[n-1]\n",
    "    \n",
    "s = Solution()\n",
    "print(s.uniquePaths(7,3))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}