LeetCode題解:Unique Path

テーマの説明
A robot is located the top-left coner of a m x n grid(marked'Start'in the diagram below)
The robot can only move eigner down or right at any point in time.The robot is trying to reach the bottom-right Coner of the grid.
How many possible unique paths are there?
Above is a 7 x 3 grid.How many possible unique paths are there?
Note:m and n will be at most 100.
Example 1:
Input:m=3,n=2 Output:3 Explanion:From the top-left coner,there ara total of 3 ways to reach the bottom-right corner:

Right->Right->Down

Right->Down->Right

Down->Right->Right Example 2:

Input:m=7,n=3 Output:28
テーマ分析
m＊nの行列がありますが、ロボットが行列の中を移動します.始点は左上隅で、終点は右下角です.毎回1歩しか移動できず、右か左にしか移動できません.全部でいくつの移動方法がありますか?
法を解く
行列の中で移動して、私達の第一印象はきっと深さ優先検索で、私達は毎回1歩移動します.右か左か、終点に行く時のパス数＋1を保証します.私達が1つのvisited配列で歩いた位置を記録します.コードは以下の通りです

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    var visited = new Array(m);
    for(var i = 0;i < m;i++) visited[i] = new Array(n);
    return recursive(0,0,m,n,visited);
};

function recursive(x,y,m,n,visited){
    if(x==m-1&&y==n-1) return 1;
    var res = 0;
    visited[x][y] = true
    if(x+1 < m && !visited[x+1][y]) res+= recursive(x+1,y,m,n, visited);
    if(y+1 < n && !visited[x][y+1]) res+= recursive(x,y+1,m,n,visited);
    visited[x][y] = false;
    return res
}

入力3 2,7 3は、正しい結果を出力し、入力20は、タイムアウトしました.タイムアウトの原因は何ですか?この解法を観察すると、7のような多くの繰り返し計算があります.私たちは点(1、1)に対して、(1、0)を下に向けて(1、1)から終点までの経路数を計算します.(0、1)を右に行くと(1、1)から終点までの経路数が計算されます.ですから、私たちはいくつかの最適化を行います.初めて(1,1)を計算した時、結果をキャッシュします.次は計算しなくてもいいです.コードは以下の通りです

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    var visited = new Array(m);
    for(var i = 0;i < m;i++) visited[i] = new Array(n);
    return recursive(0,0,m,n,visited);
};

function recursive(x,y,m,n,visited){
    if(x==m-1&&y==n-1) return 1;
    var res = 0;
    if(x+1 < m && !visited[x+1][y]) res+= recursive(x+1,y,m,n, visited);
    else if(x+1 < m &&visited[x+1][y]) res+= visited[x+1][y];
    if(y+1 < n && !visited[x][y+1]) res+= recursive(x,y+1,m,n,visited);
    else if(y+1 <n &&visited[x][y+1]) res+= visited[x][y+1];
    visited[x][y] = res;
    return res
}

コードを提出して、acを発見しました.60%を超えて提出しました.もっと最適化できますか?再帰的なものを配達に変えてもいいですか?
これは実は動的計画の思想です.中間状態を記録して、中間状態から次の状態を計算します.最後の結果を得るまで.これは多くの繰り返し計算を避けることができる.
動的計画にはいくつかの重要な要素,状態および状態遷移方程式および境界条件がある.ここで私たちの状態(i,j)は、点(i,j)から終点までの経路数を表し、(i,j)=(i＋1,j)＋(i,j＋1)、境界は一番下と一番右の二列、(m−1,i)＝1、(i,n−1)＝1.
コードは以下の通りです

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    var visited = new Array(m);
    for(var i = 0;i < m;i++) visited[i] = new Array(n);
    
    for(i=0;i < n;i++) visited[m-1][i] = 1;
    for(i = 0;i <m;i++) visited[i][n-1] = 1;
    for(i=m-2;i>=0;i--){
        for(var j = n-2;j>=0;j--){
            visited[i][j] = visited[i+1][j]+visited[i][j+1];
        }
    }
    return visited[0][0]
};

注意後から前へ巡回して、境界条件をよく処理して、100%を超えて提出します.