1269. 停在原地的方案数（动态规划）

image.png

/**
 * @param {number} steps
 * @param {number} arrLen
 * @return {number}
 */
var numWays = function(steps, arrLen) {
    const MODULO = 1000000007;
    let maxColumn = Math.min(arrLen - 1, steps);
    const dp = new Array(steps + 1).fill(0).map(() => new Array(maxColumn + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= steps; i++) {
        for (let j = 0; j <= maxColumn; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - 1 >= 0) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO;
            }
            if (j + 1 <= maxColumn) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO;
            }
        }
    }
    return dp[steps][0];
};

• 看到类似这种方案问题，基本都采用动态规划解决，看到一句话动态规划中有几个变量就维护一个几维数组去做记录

• 设定dp[i][j]做记录，表示在表示在 i 步操作之后，指针位于下标 j 的方案数，显而易见i取值大于等于0小于等于steps，j取值大于等于0小于等于min(arrLen−1,steps)

• 思考转移方程，由于每一步操作中均可以选择向左，向右或者不动，因此对于dp[i][j]而言，有dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]

• 考虑边界问题，两个点，第一初始值，由于开始指针一定在0位因此dp[0][0]毫无疑问是1而dp[0][j]是0，第二运算中的边界值，由于指针不能移动到数组范围外，则有j=0时dp[i−1][j−1]=0，当j=min(arrLen−1,steps)时dp[i−1][j+1]=0，其实换言之就是舍弃超出边界的部分，反正+0等于没有