leetcode1871 跳跃游戏 VII

思路：

动态规划+前缀和优化。

实现：

 1 class Solution
 2 {
 3 public:
 4     bool canReach(string s, int minJump, int maxJump)
 5     {
 6         int n = s.length();
 7         vector<int> sum(n + 1, 0);
 8         sum[1] = 1;
 9         int x = 0;
10         for (int i = 1; i < n; i++)
11         {
12             x = 0;
13             if (i - minJump < 0) x = 0;
14             else
15             {
16                 int l = max(0, i - maxJump), r = max(0, i - minJump);
17                 if (s[i] == '0' and sum[r + 1] - sum[l]) x = 1;
18             }
19             sum[i + 1] = sum[i] + x;
20         }
21         return x; 
22     }
23 };