360笔试（8.31）编程第二题 散步

思路

参考：https://blog.csdn.net/likewind1993/article/details/100176127

这次的两道编程题都比较简单，看到第二题大家用dfs来做的比较多，这里提供一个动态规划的思路。

设置两个长度为n+1的dp1、dp2数组，dp[i]表示某次停下是否能到第i个位置，dp[i] = 0表示不能到达，dp[i] = 1表示能到达，

1. 初始dp1[1...n] = 1，表示可以从任意的位置出发，

2. 对每走Di距离，方向可以向左走或向右走，那么走完Di距离后，可到达的位置用dp2表示，即，转移方程为：

   if (dp1[j] == 1 && j + d[i] <= n )
        dp2[j + d[i]] = 1;
   if (dp1[j] == 1 && j - d[i] >= 1 )
        dp2[j - d[i]] = 1;

3. dp1 = dp2，重复步骤2。

对每走一步都要对进行一次遍历，总共N x M次, 所以时间复杂度,空间复杂度

代码

#include <iostream>
#include <vector>
using namespace std;

void get_res(int n, int m, vector<int> & d)
{
    vector<int> dp1(n + 1, 0);
    vector<int> dp2(n + 1, 0);

    for (int i = 0; i <= n; ++i)
        dp1[i] = 1;
    for (int i = 0; i < m; ++i)
    {
        for(int j = 1; j<= n; ++j)
            dp2[j] = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (dp1[j] == 1 && j + d[i] <= n )
                dp2[j + d[i]] = 1;
            if (dp1[j] == 1 && j - d[i] >= 1 )
                dp2[j - d[i]] = 1;
        }
        dp1 = dp2;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (dp2[i] == 1)
            ++ans;
    }
    cout << ans << endl;
}

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    vector<int> D(m, 0);
    for (int i = 0; i < m; ++i)
        cin >> D[i];

    get_res(n, m, D);
    return 0;
}