1269. Number of Ways to Stay in the Same Place After Some Steps
你有一個指標在陣列上移動，指標起點在0
每次操作可以進行下列三種選擇:往左一格、往右一格、待命。
指標操作後必須不能超出陣列範圍
求在arrLen長度的陣列進行steps次操作下
指標最後回到0 一共的可能次數
例題1: steps = 3, arrLen = 2, 答: 4
所有可能如下: 右停左、停停停、右左停、停右左
例題2: steps = 2, arrLen = 4, 答: 2
所有可能如下: 停停、右左
例題3: steps = 4, arrLen = 2, 答:8
First think:
排列組合的問題，所有可能 - 超出陣列長度 - 指針移動到負 + 超出陣列且移動到負
所有可能:
右的次數從0次到steps/2次去排列 然後左永遠=右
例如例題一 右=0:停停停 右=1:右停左、右左停、停右左
超出陣列長度:
右的次數 > 陣列長度/2
指針移動到負:
任何左先出現的次數>右 例如左停右
仔細研究了一下後 發現超難 很難用簡單的算式去列出解答
所以這應該不是解決方法
後來發現移動問題有另一種解法
就是高中的捷徑問題
每次走路可以往上或往右走，求左下走到右上的所有可能
隨便找一張高中例題的圖: https://i.imgur.com/XcRGvey.png
同樣的這一題也可以用類似的概念去解決
我們畫出一個寬=陣列長度 長=步驟數+1的方格
然後從左上開始走
每次操作可以往下(停住) 或是往左下(指針往左) 或是往右下(指針往右)
把例題1畫圖出來的話是這樣: https://i.imgur.com/mFy0nqK.png
還沒有開始走的時候指針只可能會在起點
所以起始陣列列出來是100
走第一步的可能是右或停
這時候指針的位置可能會在0或1
因此第零步的起點1就要往下加、往右下加
第一步的陣列就會是110
之後都以此類推
舉例來說圖片中第三步[4,5,3]裡面的5
就是第二步的2+2+1(左邊一格往右走 或是停 或是右邊一格往左走)
https://i.imgur.com/boSrR7b.png
把數字全部列出來之後
最左下的數字就是走到最後一步之後 指針在0的可能次數
第一題的答案我們就可以得出是4
到這邊就可以解答了
不過還有可以優化的地方
https://i.imgur.com/rCnETTd.png
圖片中藍色線的右上以及紅色線的右下都是可以不用計算的地方
在路剛開始走的時候右上角一定不會有數字
非0的數字跟走的步驟數成正比 所以藍色線的右上一定都是0
然後我們想知道最後指針在0的可能性
所以紅線以右的數字都是不可能會回到0的數字就可以不用計算
把這兩邊排除之後計算量可以變成原本的一半左右
最後還有一點
題目要求的數字可能會太大
所以要求答案要輸出可能次數除以10^9+7的餘數
本來我想說全部算完取餘丟出去就好
但是發現好像數字太大會溢位 沒辦法得出正確答案
所以就改成每次算完就取一次餘
相加取餘 = 取餘之後相加再取餘
自己算式列一下就能證明了
(這好像跟輾轉相除法是類似的東西)
TS code:
function numWays(steps: number, arrLen: number): number {
const results: number[][] = new Array(2)
let arrIndex = 1
for (let index = 0; index < 2; index++) {
results[index] = new Array(steps + 1).fill(0)
results[index][0] = 1
}
for (let time = 1; time <= Math.ceil(steps / 2); time++) {
const prevArr = results[arrIndex]
arrIndex = (arrIndex + 1) % 2
const currentArr = results[arrIndex]
for (
let index = 0;
(index < steps &&
index < time + 1 &&
index < arrLen);
index++) {
currentArr[index] = prevArr[index] + prevArr[index + 1]
if (index > 0) currentArr[index] += prevArr[index - 1]
if (currentArr[index] >= 1000000007) currentArr[index] %= 1000000007
}
}
for (let time = Math.floor(steps / 2); time > 0; time