主題
題目連結(jié)：
題目意譯：
你被給定兩正整數(shù) startPos 和 endPos。一開始，你站在無限延伸的數(shù)線上的位置 startPos。在一步之中，你可以往左或往右一單位距離。
給定一正整數(shù) k，回傳從 startPos 以恰好 k 步抵達(dá) endPos 的相異方法數(shù)。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
兩種方法如果移動(dòng)順序不完全一致，則兩者視為相異。
注意到數(shù)線包含著負(fù)整數(shù)。
限制：
1 ≦ startPos, endPos, k ≦ 1000
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： startPos = 1, endPos = 2, k = 3
輸出： 3
解釋： 我們可恰好 3 步從位置 1 抵達(dá) 2，方法為有三種：
- 1 → 2 → 3 → 2。
- 1 → 2 → 1 → 2。
- 1 → 0 → 1 → 2。
可以證明沒有其他可能的方法存在，所以我們回傳 3。
範(fàn)例 2：
輸入： startPos = 2, endPos = 5, k = 10
輸出： 0
解釋： 不可能在恰好 10 從位置 2 抵達(dá) 5。
解題思維：
令 d = abs(endPos - startPos)，即兩個(gè)位置之間的距離值。
如果 k < d 或是 d 與 k 的奇偶性不同（即一奇一偶），則不可能從 startPos 用剛好 k 步走到 endPos。原因很明顯：
k < d 則當(dāng)然不可能到，因?yàn)橐徊街荒軇?dòng)一單位、
k = d 也很顯然，因?yàn)閯倓偤每梢缘诌_(dá)、
而 k > d，則可以先走 d 步到 endPos，然後在 endPos 和 endPos + 1 這兩個(gè)位置之間交替來把剩下的步數(shù)用掉。因此如果 k 和 d 的奇偶性不同，則最後你會(huì)停在 endPos + 1 這個(gè)位置上，無法停在 endPos。
假設(shè)現(xiàn)在 startPos < endPos（如果 startPos > endPos，則將之後的敘述中的「左」換成「右」、「右」換成「左」），則我們過程中「往右」d + (k - d) ÷ 2 單位（或等價(jià)於 (k + d) ÷ 2 單位）、「往左」(k - d) ÷ 2 單位。然後我們把這些「往左」、「往右」各自視為實(shí)際存在的物件（左、右箭頭等）。
因此走恰好 k 步到 endPos 的方法數(shù)等價(jià)於這些左右箭頭的排列組合，其值為
k! ÷ (((k + d) ÷ 2)! × ((k - d) ÷ 2)!)
其中「!」代表階乘運(yùn)算（Factorial）。不過當(dāng)然由於過程中需要對(duì) 10 ^ 9 + 7 取模，因此需要牽涉到求階乘的模反元素之運(yùn)算（可以參見這題）。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
