好久不写笔记。力扣周赛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 得到的数值取反，对应当前数组外的另一个数组。
