leetcode1269 动态规划

好久不写笔记。力扣周赛164的最后一题看起来很难，但是看过解答后感觉可以做出，困扰的原因在于没有想到用动态规划解决。题目思路和官方的编码方式很值得学习，在此记录。
题目链接
官方解答

用动态规划解答

对于统计方案数的问题，应该想到动态规划。移动次数与数组长度可以做为指针i，j来构建动态数组。
初始状态：f[0][0]=1
状态方程：f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1]
备注:j-1>=0,j+1<arrLen,结果要取模
返回值:f[steps][0]
这时想到时空复杂度应该为 steps * arrLen，arrLen 过大会导致动态数组和运算时间过大。可 arrLen 若大于 steps，题目中的指针是无法到达的，因此可以将 arrLen 减小为 steps 。时空复杂度变为 steps * min(arrLen,steps)。
官方代码的风格简单明了:

class Solution {
private:
    static const int mod = 1000000007;     //提前定义模
    
public:
    int numWays(int steps, int arrLen) {
        arrLen = min(arrLen, steps + 1);
        vector<vector<int>> f(steps + 1, vector<int>(arrLen));
        f[0][0] = 1;
        for (int i = 1; i <= steps; ++i) {
            for (int j = 0; j < arrLen; ++j) {
                for (int k = -1; k <= 1; ++k) {
                    if (j - k >= 0 && j - k < arrLen) {
                        f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
                    }
                }
            }
        }
        return f[steps][0];
    }
};

使用 vector<vector<int>> f(steps + 1, vector<int>(arrLen)); 构建数组。
理解如下: 构建一个以vector<int>为元素类型的vector容器f，f包含 (steps+1) 个 vector<int> 类型对象，每个对象都是一个新创立的vector<int>对象的拷贝，新创立的vector<int>对象默认初始化包含arrLen个0。(参考阅读)
本题也可以使用数组构建，但vector较数组有可初始化，可动态分配，包含命令等优点。

空间优化方案

通过状态方程可以看出，每一次steps的增加，动态数组都根据上一次更新得到的数值更新，上一次更新前的数值不会再被使用，因此可不必构建
steps * min(arrLen,steps) 大小的数组， 2*min(arrLen,steps) 大小已经足够。
我们可以用奇偶判断的方式不断重用两个数组 (之前小比赛学到的 i&1 的技巧)。
官方代码：

class Solution {
private:
    static const int mod = 1000000007;
    
public:
    int numWays(int steps, int arrLen) {
        arrLen = min(arrLen, steps + 1);
        vector<vector<int>> f(2, vector<int>(steps + 1));  //此处steps + 1应为arrLen。
        f[0][0] = 1;
        for (int i = 1; i <= steps; ++i) {
            fill(f[i & 1].begin(), f[i & 1].end(), 0);
            for (int j = 0; j < arrLen; ++j) {
                for (int k = -1; k <= 1; ++k) {
                    if (j - k >= 0 && j - k < arrLen) {
                        f[i & 1][j] = (f[i & 1][j] + f[(i & 1) ^ 1][j - k]) % mod;
                    }
                }
            }
        }
        return f[steps & 1][0];
    }
};

vector容器可以使用fill函数初始化数值，若使用数组则用memset。
i&1 将 i 与1 进行二进制的与或计算，将直接得到i的最低位值，正好用于数组的0，1下标。
(i&1)^1 将 i&1 得到的数值取反，对应当前数组外的另一个数组。