【Day17】1269.停在原地的方案数

1269. 停在原地的方案数

有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。

每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。

给你两个整数 steps 和 arrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。

由于答案可能会很大,请返回方案数 模 10^9 + 7 后的结果。

示例 1:

输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动

示例 2:

输入:steps = 2, arrLen = 4
输出:2
解释:2 步后,总共有 2 种不同的方法可以停在索引 0 处。
向右,向左
不动,不动

示例 3:

输入:steps = 4, arrLen = 2
输出:8

提示:

1 <= steps <= 500
1 <= arrLen <= 10^6

题解:

暴力递归

pos表示移动的index,st表示当前还剩步数。结果超时- _ -

class Solution {
 public:
  const int N = 1000000007;
  int numWays(int steps, int arrLen) { 
      int res = dfs(steps, arrLen, 0);
      return res % N; 
  }

  int dfs(int st, int arrLen, int pos) {
    if (st < 0 || pos < 0 || pos >= arrLen) return 0;
    if (st == 0 && pos == 0) {
      return 1;
    }
    int ans = 0;
    if (pos >= 0 && pos <= arrLen - 1)
      // 不动
      ans = dfs(st - 1, arrLen, pos);
    if (pos >= 1)
      // 向左
      ans += dfs(st - 1, arrLen, pos - 1);
    if (pos <= arrLen - 2)
      // 向右
      ans += dfs(st- 1, arrLen, pos + 1);
    return ans;
  }
};

记忆化搜索

一开始开辟空间太大,过不了,发现开辟很大空间后,使用map性能比vector好,而实际只需要开辟steps*steps即可。

int memo[505][505];
// vector> memo;
class Solution {
 public:
  static const int N = 1000000007;
  int numWays(int steps, int arrLen) { 
      memset(memo, -1, sizeof(memo));
    //   memo = vector>(505, vector(505,-1));
      int res = dfs(steps, arrLen, 0);
      return res % N; 
  }

  int dfs(int st, int arrLen, int pos) {
    if (st < 0 || pos < 0 || pos >= arrLen) return 0;
    if (memo[st][pos] != -1) return memo[st][pos];
    if (st == 0 && pos == 0) {
      return memo[st][pos] = 1;
    }
    int ans = 0;
    if (pos >= 0 && pos <= arrLen - 1) 
      // 不动
      ans = dfs(st - 1, arrLen, pos) % N;
    if (pos >= 1)
      // 向左
      ans =  ans % N + dfs(st - 1, arrLen, pos - 1) % N;
    if (pos <= arrLen - 2)
      // 向右
      ans = ans % N + dfs(st- 1, arrLen, pos + 1) % N;
    return memo[st][pos] = ans;
  }
};

动态规划

class Solution {
 public:
  static const int N = 1000000007;
  int numWays(int steps, int arrLen) { 
      int maxLen = min(steps, arrLen);
      long long dp[steps + 1][maxLen + 1];
      memset(dp, 0, sizeof dp);
      dp[1][0] = 1;
      dp[1][1] = 1; // step=1 pos=1

      for (int s = 1; s <= steps; s++) {
          for (int l = 0; l < maxLen; l++) {
            // 原地
                dp[s][l] = dp[s][l] + dp[s - 1][l];
            // 右
                dp[s][l] = dp[s][l]  + dp[s - 1][l + 1];
            // 左

                if (l - 1 >= 0)
                    dp[s][l] =  dp[s][l] + dp[s - 1][l - 1];

              dp[s][l] %= N;
          }
      }     
      return dp[steps][0]; 
  }
};

   转载规则


《【Day17】1269.停在原地的方案数》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day18】12.整数转罗马数字 【Day18】12.整数转罗马数字
12. 整数转罗马数字罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L
2021-05-14
下一篇 
【Day16】1310.子数组异或查询 【Day16】1310.子数组异或查询
1310. 子数组异或查询有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]。 对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr[Li] xor ar
2021-05-12
  目录