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

[LeetCode]62.Unique Paths

編輯:關於C++

【題目】

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 3 x 7 grid. How many pZ喎?/kf/ware/vc/" target="_blank" class="keylink">vc3NpYmxlIHVuaXF1ZSBwYXRocyBhcmUgdGhlcmU/PC9wPgo8cD4KTm90ZTogbSBhbmQgbiB3aWxsIGJlIGF0IG1vc3QgMTAwLjwvcD4KPGg0PqG+y7zCt6G/PC9oND4KPHA+yehzW2ldW2pdIM6qtNPG8LXjtb2jqGksaqOpzrvWw7SmtcTCt762yv2hozwvcD4KPHA+zai5/bfWzva1w7W9o7q12tK70NCjrLXa0rvB0La8zqoxPC9wPgo8cD61vcbky/vOu9bDtKajqGksaqOpo7q1vbTvzrvWw6OoaSxqo6nWu8TctNPJz8Pmu/LV39fzw+a5/cC0o6zS8rTLvva2qLW9zrvWw6OoaSxqo6m1xMK3vrbK/dPJtb2078nPw+bOu9bDo6hpLTEsaqOptcTCt762yv26zbW9tO/X88PmzrvWw6OoaSxqLTGjqbXEwre+tsv5vva2qLXEoaM8L3A+CjxwPte0zKzXqtLGt72zzKO6PC9wPgo8cD5zW2ldW2pdID0gc1tpLTFdW2pdICYjNDM7IHNbaV1bai0xXTwvcD4KPHA+yrG85Li01NO2yKO6TyhuXjIpICC/1bzkuLTU07bIo7pPKG5eMik8L3A+CjxoND6hvrT6wuuhvzwvaDQ+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;"> /*------------------------------------ * 日期:2015-02-03 * 作者:SJF0115 * 題目: 62.Unique Paths * 網址:https://oj.leetcode.com/problems/unique-paths/ * 結果:AC * 來源:LeetCode * 博客: ---------------------------------------*/ #include #include #include #include using namespace std; class Solution { public: int uniquePaths(int m, int n) { int s[m][n]; for(int i = 0;i < m;++i){ for(int j = 0;j < n;++j){ if(i == 0|| j == 0){ s[i][j] = 1; }//if else{ s[i][j] = s[i-1][j] + s[i][j-1]; }//esle }//for }//for return s[m-1][n-1]; } }; int main(){ Solution s; int m = 3; int n = 4; int result = s.uniquePaths(m,n); // 輸出 cout<

\

【思路二】

使用空間輪轉的思路,節省空間。

狀態轉移方程:

s[j] = s[j] + s[j-1]

時間復雜度:O(n^2) 空間復雜度:O(n)

【代碼二】

    /*------------------------------------
    *   日期:2015-02-03
    *   作者:SJF0115
    *   題目: 62.Unique Paths
    *   網址:https://oj.leetcode.com/problems/unique-paths/
    *   結果:AC
    *   來源:LeetCode
    *   博客:
    ---------------------------------------*/
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            int s[n];
            // 第一行全為1
            for(int i = 0;i < n;++i){
                s[i] = 1;
            }//for
            // 從第二行開始
            for(int i = 1;i < m;++i){
                // 第i行第j個格
                for(int j = 1;j < n;++j){
                    s[j] = s[j] + s[j-1];
                }//for
            }//for
            return s[n-1];
        }
    };


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