程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Unique Paths

leetcode筆記:Unique Paths

編輯:C++入門知識

leetcode筆記:Unique Paths


一. 題目描述

A robot is located at the top-left corner of a m  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 3 * 7 grid. How many possible unique paths are there?<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPk5vdGU6IG0gYW5kIG4gd2lsbCBiZSBhdCBtb3N0IDEwMC48L3A+DQo8cD48c3Ryb25nPrb+LiDM4sS/t9bO9jwvc3Ryb25nPjwvcD4NCjxwPszixL+1xLTz0uLKx7v6xvfIy9Ta0ru49r7Y1fPA79ffwrejrLnmtqjG8LXjoaLW1bXjus3X38K3tcS3vc/yo6zOytffzerIq7PM19y5stPQvLjW1tfft6iho7jDzOLK18/Iz+u1vdPDye62yNPFz8jL0cv3wLTX9qOstavKx73hufvKx7OsyrGho7/JyrnTw7avzKy55ruuwLTX9qOsyejXtMyszqo8Y29kZT5rW2ldW2pdPC9jb2RlPqOsse3KvrTTxvC14zxjb2RlPigwLCAwKTwvY29kZT61vbTvPGNvZGU+KGksIGopPC9jb2RlPrXEwrfP38z1yv2jrNTy17TMrNeq0sa3vbPMzqqjujwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> k[i][j]=k[i-1][j]+k[i][j-1]

使用動態規劃時,需注意邊界條件的設定。

以下代碼使用new創建一維數組(數組大小為m * n)並將其作為二維數組使用,第i行、j列的元素可表示為:k[i * n + j] ,這樣創建二維數組的好處是內存連續,但表示不夠直觀。

三. 示例代碼

#include 

using namespace std;

class Solution

{
public:
    // 深搜,會超時
    int uniquePaths(int m, int n)
    {
        if (m <= 0 || n <= 0)
            return 0;

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

        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }

    // 動態規劃
    int uniquePaths2(int m, int n) // 動態規劃
    {
        int *k = new int[m * n];

        // 到兩條邊處各點的走法只有一種
        for (int i = 0; i < m; ++i)
            k[i * n] = 1;
        for (int j = 0; j < n; ++j)
            k[j] = 1;

        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                k[i * n + j] = k[(i - 1) * n + j] + k[i * n + j - 1];
            }
        }

        int result = k[(m - 1) * n + n - 1];
        delete [] k;
        return result;
    }
};

這裡寫圖片描述

四. 小結

事實上,如果只是求出路線的種數,完全可以將該問題轉化為數學問題。假設一個mn列的矩陣,機器人從左上走到右下總共需要的步數是m + n - 2,其中向下走的步數是m - 1,因此問題變成了在m + n - 2個操作中,選擇m – 1個時間點向下走,選擇方式有多少種,可用以下公式算出:

這裡寫圖片描述

若考慮向右走的情況,則步數為n - 1,問題也可解釋為在m + n - 2個操作中,選擇n – 1個時間點向右走的方法有多少種,公式:

這裡寫圖片描述

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved