05-30 08:38 阅读 133

关注

leetcode1871 跳跃游戏 VII

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             else15             {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 };

来源https://www.cnblogs.com/wangyiming/p/14826203.html