62.
一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ），
機器人每次只能向下或者向右移動一步，機器人試圖達到網格的右下角（在下圖中標記為“Finish”），
問總共有多少條不同的路徑？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths
思路1：時間換空間；
將問題轉換為數學問題，以（7,3）為例，往右走6次，往下走2次，即有（6+2）！種排列組合，去掉重復組合6！和2！，結果為8! / 6! / 2!，再根據規律
1*2*3*4*5*6*7*8
1*2*3*4*5*6
1*2
第一個式子可以抵消第二個或第三個式子，而且抵消后，式子1剩下的數剛好和剩下的式子數字數量相等，不必每次都從開始進行計算
/** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function(m, n) { let sum=1; let j=1; let memory=1; for(let i=m;i<=m+n-2;i++){ if(i%j==0){ sum*=i/j; } else{ sum*=i; memory*=j; } j++; } return sum/memory; };
思路2：空間換時間，沒有那么多花里胡哨，直接按公式計算
/** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function(m, n) { return mult(m+n-2)/mult(m-1)/mult(n-1); function mult(data){ return data<=1? 1: data*mult(data-1); } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/136666.html
標籤：其他
上一篇：CodeForces 1251A --- Broken Keyboard
下一篇：計算及校驗海明碼的3個舉例