先端転職面接アルゴリズム——動的計画

ブログの参考
今日のトップの銀の国章の先生の《js版のデータの構造とアルゴリズム》
Part 1改编自《漫画计算方法》原作者:程序员小灰
前言
バックグラウンド開発者に比べて
アルゴリズムは私たちのフロントエンド開発者の弱点です.
ここ2年、インターネット業界の競争がますます激しくなるにつれて、市場の先端ポストに対するアルゴリズムの要求も一定の向上があった.
大学3年生がテンセントの募集面接に参加したとき、いくつかの一般的なソートアルゴリズムしか用意していなかったのを覚えていますが、今年は今日のトップを含む多くの大手工場の先端筆記試験の問題に「欲張りアルゴリズム」「動的計画」「分治アルゴリズム」などの段階的なアルゴリズムの問題が出てきました.このような進歩的なアルゴリズム問題に対して,事前準備なしに現場で対応することはそれほど簡単ではない.
もしあなたがこれらのアルゴリズムを聞いたことがないのに、また大きな工場に入りたいなら、迷わないで、髪が落ちないうちに急いで勉強しましょう.
                                         
このブログは2つの部分に分かれています

Part 1:漫画のイメージを通してダイナミックな企画を語る思想

Part 2:ダイナミックプランニングに関するLeetCodeの本題に合わせて実戦演習

読み終わったら、ダイナミックな計画の方法を徹底的に把握し、活用することを学ぶと信じています.
Part 1:漫画の理解
             
           
              
         
一つ一つ一つ一つ一つ一つ
             
            
    
タイトル:
10冊の本しか収容できない単層本棚があり、毎回1冊か2冊しか入れられません.プログラムで本棚を埋め尽くす方法を求めます.
例えば、本を1冊ずつ10回置くのが一つの方法です.1,1,1,1,1,1,1,1,1,1,1,1,1と簡単に書くことができます.
例えば、本を2冊ずつ5回置くのは別の方法です.2,2,2,2,2,2と簡単に書くことができます.
もちろん、それ以外にもいろいろな方法があります.
              
         
         
             
          
         
一つ一つ一つ一つ一つ一つ
             
            
           
          
          
            
    
1つ目:
2つ目:
 
            
             
        
      
      
 
ここでは皆さんの理解を容易にするために、もう一つの例を挙げます.
図示のようにroad 1またはroad 2の2つの経路のみで終点に到達すると仮定する
(本を置く最後のステップを2冊と1冊に分ける場合に相当)
到着road 1にはx本の経路(0~8本の放法数F(8)に相当)がある.
到着road 2にはy本の経路(0~9本の放法数F(9)に相当)がある
では終点に到達する可能性はx+y(すなわち,我々が前に導いたF(10)=F(9)+F(8))である.
        
             
     
  
          
               
       F(1) = 1;
       F(2) = 2;
       F(n) = F(n-1)+F(n-2)(n>=3)
          
         
        
         
          
皆さんが見終わったらきっとダイナミックな計画について初歩的な認識を持っていると信じています.
ここではまずこの問題のコードを書いてみてください
次に、LeetCodeの実戦原題を通じて、動的計画に対する理解を深めましょう.
Part 2:実戦演習
異なる経路II
LeetCode第63題原題アドレス
問題の難易度は中くらいだ
タイトルの説明
ロボットはm x nメッシュの左上隅にあります(開始点は下図で「Start」と表記されています).
ロボットは毎回、下または右に1歩しか移動できません.ロボットはメッシュの右下隅に到達しようとします(下図では「Finish」と表記されています).
グリッドに障害物があることを考慮します.では、左上から右下には何本の異なるパスがありますか?
グリッド内の障害物と空の位置はそれぞれ1および0で表します.
説明:mとnの値はいずれも100を超えない.
インスタンス1
入力:
 [ 
   [0,0,0], 
   [0,1,0],
   [0,0,0] 
]出力:2
解釈:3 x 3メッシュの真ん中に障害物があります.
左上から右下に2つの異なるパスがあります.
1.右->右->下->下
2.下へ->下へ->右へ->右へ
テーマ解析
皆さんが見たと思いますが、私たちのこの問題は私たちの漫画のプレゼンテーションのテーマとほぼ一致しています.
しかし、それはまた少し難易度を高めて、私たちは障害物の状況を考慮する必要があります.
私たちが前に述べた動的計画の3要素「最適サブ構造」「境界」と「状態遷移式」を覚えていますか.
タイトルの画像を例に挙げます.
障害物を考慮しない場合、ダイナミックプランニングの考え方を利用して、ゴールに着くにはいくつかの状況がありますか?
明らかに2つです.終点の上または終点の左側から到着します.
7*3行列
この7*3の行列の終点F(7*3)の最適サブ構造はF(6*3)とF(7*2)であることを容易に導いた.
これでその状態遷移式も一目瞭然である:F(m*n)=F(m-1*n)+F(m*n-1)
最後に、その境界状況を考えてみましょう.
評論区の学友の指摘を経て、実は私達の前に考慮したF(2*2)の境界の情況は引き続き下に分けて1列と1行の即ちF(1*2)+F(2*1)の2種類の情況に分けることができます.
すべてのF(m*n)の行列は最後に1行と1列に分割できるので,ここでは境界の場合は2種類しかない.

第1の境界F(1*n)すなわち1行n列

このときこの行はいずれかの障害物があると通過できません
   

第2の境界F(n*1)すなわちn行1列

このときこの列に障害物が1つあると通過できません
     
コード実装

export default (arr) => {
  let dp = (m, n) => {
    //              1(   )，             1，          ，
    //     0
    if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
      return 0
    }
    //    
    if (m < 2 || n < 2) {
      //       1 n 
      if (m < 2) {
        return arr[m - 1].includes(1) ? 0 : 1
      } else {
        //       n 1 
        for (let i = 0; i < m; i++) {
          if (arr[i][0] === 1) {
            return 0
          }
        }
        return 1
      }
    } else {
      //   
      return dp(m - 1, n) + dp(m, n - 1)
    }
  }
  return dp(arr.length, arr[0].length)
}

補足:時間複雑度分析
もんだいぶんせき
学生たちがコメントエリアで提起した問題に感謝します.
まず、上のコードは問題ありませんが、LeetCodeの27番目のテスト例では時間制限を超えています.
この試験例は比較的複雑で,33*22の二次元行列である.
では、なぜマトリクスが一定の長さに達すると、私たちの方法の時間の複雑さが高すぎるのでしょうか.
まず、私たちの考えを振り返ってみましょう.

F(10) = F(9) + F(8)             

F(9) = F(8) + F(7)      

F(9)を分解するとF(10)は

 F(8) + F(8) + F(7)

F(8)はまた=F(7)+F(6)である.
では、F(8)分解F(10)を引き続き

F(7) + F(7) +F(7) + F(6) + F(6)

気づいたか?
下向きに分割すればするほど重複するので、F(n)の値を一度増やしたほうがいいと思いますか?
しかし、ここで注意しなければならないのは、
F(n)は単純に値の参照ではなく、再帰関数であり、繰り返すたびにF関数を再実行します.
時間の複雑さの具体的な計算については議論しません
しかしここでは、これまでの方法の時間的複雑さはO(2^n)であることをお伝えします.
では、どのように改善しますか.
構想を打ち出す.
ここで2つのアイデアを提案します.皆さんも自分で書いてみてください.

は、毎回算出された値、すなわち、F(9)、F(8)、F(7)を記録する.の値は、再帰関数を再び呼び出すことなく、以前に計算されたデータがあるたびに直接値を取ります.

は、下から上へ(始点から終点まで)計算され、前の2つのデータのみに依存するため、2つの変数によって前の2回のデータのみを保存すればよい.例えば、F(3)はF(1)とF(2)のみに依存し、計算F(6)はF(5)とF(4)のみに依存する.

コード最適化

//       
arr => {
    //   
    let n = arr.length;
    if(!n){
        return 0;
    }
    //   
    let m = arr[0].length;
    //          
    if(arr[0][0] === 1 || arr[n - 1][m - 1] === 1){
        return 0;
    }
    //               
    var rode= [];
    //      
    for(let i = 0; i < n; i++){
        rode[i] = [];    //           
        for(let j = 0; j < m; j++){
            //         ，            0
            if(arr[i][j] === 1){
                rode[i][j] = 0;
            } else if(i === 0){
                //                        
                rode[i][j] = rode[i][j - 1] === 0 ? 0 : 1;
            } else if(j === 0){
                //                                        
                rode[i][j] = rode[i - 1][j] === 0 ? 0 : 1;
            } else {
                //     
                rode[i][j] = rode[i - 1][j] + rode[i][j - 1];
            }
        }
    }
    return rode[n - 1][m - 1];
}

リファレンス

プログラマーの灰--漫画:ダイナミックな計画とは何ですか.

今日のトップシルバーエンブレム先生-js版データ構造とアルゴリズム

皆さんもFE_を参考にYuanさんはこのブログについて補足しました:フロントエンド面接アルゴリズム-ダイナミックプランニング

まとめ
皆さんは発見しましたか?ダイナミックプランニングの3要素「最適サブ構造」「境界」と「状態遷移式」を把握しました.
その後,動的計画のアルゴリズム問題を解決することは難しくない.しかし、その中の思想は私たちがよく消化吸収する必要がある.
これからこのような問題に直面しても、あなたはすぐに解決できると信じています.
転載先:https://juejin.im/post/5cde316f6fb9a07ed9118f01