一道dp的三次优化（时间+空间）

链接：D. Chip Move

题意：

一开始处于坐标轴的原点，给定了数字K，第一次跳K的倍数步，第二次K + 1的倍数步，…一直这样跳下去。

问点1~n，到达这些位置的走法分别是多少。

做法：

一、（会MLE，然后显然也是TLE的…）
f[i][j]表示到达第i个点的时候，一共走了j步，这样的dp方程的转移非常好想，直接考虑j - 1步的时候能从哪些位置转移过来就好了。直接上代码。

其中b数组的意思是到这个点最多可以跳b[i]步。

可以看到最内层就是枚举步长的倍数，进行一个非常暴力的转移了。

int a[N], b[N];
int f[N][632], ans[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = k, j = 1; i <= n; i += k + j, j++) b[i] = b[i - k - j + 1] + 1;
    for (int i = 1; i <= n; i++) b[i] = max(b[i], b[i - 1]);  //b[200000] = 631
	f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= b[i]; j++)
        {
			for (int s = 1; i - s * (k + j - 1) >= 0; s++)
            {
                f[i][j] += f[i - s * (k + j - 1)][j - 1];
                f[i][j] %= mod;
            }
			ans[i] = (ans[i] + f[i][j]) % mod;
        }
    }
	for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二、

考虑优化最内层的枚举倍数的循环，可以用调和级数，但还是会MLE和TLE，这里就不展开代码了。

三、（不会TLE，但会MLE）

这次彻底优化时间复杂度，最内层的枚举倍数，设step = s * (k + j - 1)，tle代码会去找 i - 1 * step，i - 2 * step…，然后是从j - 1步转移而来。但是这样是有大量的重复计算了，这些里面有相当一部分，被f[i - 1* step] [j]也进行过计算，所以可以这样优化了：

很像完全背包的转移方程的优化，关于完全背包，依稀记得他的n3优化到n2的推理，在白书上有，进阶指南没写这部分优化，有点子可惜。。

int a[N], b[N];
int f[N][632], ans[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = k, j = 1; i <= n; i += k + j, j++) b[i] = b[i - k - j + 1] + 1;
    for (int i = 1; i <= n; i++) b[i] = max(b[i], b[i - 1]);  //b[200000] = 631
	f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= b[i]; j++)
        {
			// for (int s = 1; i - s * (k + j - 1) >= 0; s++)  //这是没有优化时间复杂度的
            // {
            //     f[i][j] += f[i - s * (k + j - 1)][j - 1];
            //     f[i][j] %= mod;
            // }
			int from = i - (k + j - 1);
			if (from < 0) continue;
			f[i][j] = (f[from][j] + f[from][j - 1]) % mod;   //优化时间复杂度后可以这样转移
			ans[i] = (ans[i] + f[i][j]) % mod;
        }
    }
	for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

四、（成功AC）

考虑优化空间了，这里注意到f[i][j] = (f[from][j] + f[from][j - 1]) % mod;，第二维只会从j和j-1，那就考虑优化他们了。

首先说一下代码里的两层循环为什么可以互换位置，循环换一下顺序，不影响结果，是因为只要保证计算某个状态时候，被转移的状态全部计算过了就行，这个题目，换一下两维枚举顺序，显然可以保证这一点。

然后再说一下为什么第16行要进行一个清0，因为待会儿会被累加进ans数组，而上一次的结果是不能留在这一次的。

快乐上代码了：

int a[N], b[N];
int f[N][2], ans[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = k, j = 1; i <= n; i += k + j, j++) b[i] = b[i - k - j + 1] + 1;
    for (int i = 1; i <= n; i++) b[i] = max(b[i], b[i - 1]);
    f[0][0] = 1;
    for (int j = 1; j <= b[n]; j++)
    {
        for (int i = 0; i <= n; i++) f[i][j & 1] = 0;
        for (int i = 1; i <= n; i++)
        {
			int from = i - (k + j - 1);
            if (from < 0) continue;
			f[i][j & 1] = (f[from][j & 1] + f[from][!(j & 1)]) % mod;
			ans[i] = (ans[i] + f[i][j & 1]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22