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