牛牛这次又在玩一个游戏，一个横版过关小游戏。
牛牛需要控制一个角色，通过不断地跳跃，通过河流才可以过关。每次只能向前跳跃，不能返回。每次跳跃的时候可以选择一个跳跃的长度，但是这个长度需要大于1但不能大于d。
河流中间有几块石头，这几块石头是跳跃的时候的唯一落脚点，如果该角色不小心跳到了河里，游戏就结束了。
随着游戏难度的升级，牛牛渐渐的已经无法赢得游戏，所以他想请你帮忙，该角色一开始在起点(起点和终点一定保证有一个石头)，给定每次跳跃的最大长度d和一个只含有0和1的字符串s(0代表河1代表石子)，返回牛牛最少需要控制该角色多少次才可以到达终点，如果到达不了，返回-1。

我们可以构造出一个贪心策略，让该角色从步长为d开始尝试，如果落脚点为河，那么就d--，继续尝试。不断地去遍历整个状态，很类似于递归，递归的入口可以设置成step=1，递归的出口可以设置成step == len(s)。
这个策略可以使用dfs来实现，代码如下：
时间复杂度图片说明
空间复杂度图片说明 

class Solution {
public:
    int ans = 0;
    bool dfs(int step, int d, string s)
    {
        if (step == s.size())
        {
            return 1;
        }
        for (int i = d; i >= 1; --i)
        {

            if ((step + i <= s.size()) && s[step + i - 1] - '0')
            {
                step += i;
                ans++;
                if (dfs(step, d, s))
                    return 1;
            }
        }
        return 0;
    }
    /**
     * 返回牛牛最少需要控制该角色多少次才可以到达终点，如果到达不了，返回-1。
     * @param d int整型 代表该角色每次跳跃的最大长度
     * @param s string字符串 代表该关卡河流和石子的分布(0代表河1代表石子)
     * @return int整型
     */
    int solve(int d, string s) {
        // write code here
        ans = 0;
        if (!dfs(1, d, s)) //起始step在第1个位置
        {
            return -1;
        }
        return ans;
    }
};

不过上述代码过不了所有的测试用例，递归最后会爆栈，OOM。
事实上，既然递归可以的话，我们也可以采用一种完全使用迭代的贪心策略，使用上述一致的思路(之前描述有误，其实是O(n)，接纳出题人的建议将数据范围扩大到了1e6,下面代码也是完全可以过的)：
代码如下：
时间复杂度图片说明
空间复杂度图片说明 

class Solution {
public:
    /**
     * 返回牛牛最少需要控制该角色多少次才可以到达终点，如果到达不了，返回-1。
     * @param d int整型 代表该角色每次跳跃的最大长度
     * @param s string字符串 代表该关卡河流和石子的分布(0代表河1代表石子)
     * @return int整型
     */
    int solve(int d, string s)
    {
        int n = s.size();
        int ans = 0;
        int pos = 1; //当前位置
        while (pos < n)
        {
            int i = min(n - 1, pos + d - 1);
            while (s[i] == '0') //依次尝试
                i--;
            if (i + 1 == pos)
            {
                return -1;
            }
            pos = i + 1;
            ans++;
        }
        return ans;
    }
};

感谢两位出题人的代码：都是O(n)解法

int solve(int d, string s)
{
    int len = s.length();
    if (len == 1)
        return 0;
    int step = 0, i = 0;
    while (1)
    {
        if (i + d >= len - 1)
        {
            step++;
            break;
        }
        int find = -1;
        for (int j = 1; j <= d; j++)
        {
            if (s[i + j] == '1')
                find = i + j;
        }
        if (find == -1)
        {
            step = -1;
            break;
        }

        i = find;
        step++;
    }
    return step;
}

java版本

public int solve(int d, String s)
{
    // write code here
    ArrayList<Integer> t = new ArrayList<Integer>();
    int i, j = 0, cnt = 0;

    for (i = 0; i < s.length(); i++)
    {
        if (s.charAt(i) == '1')
            t.add(i);
    }
    int temp = 0;
    for (i = 0; i < t.size() - 1; i++)
    {
        if (t.get(i + 1) - t.get(temp) > d)
        {
            if (i == temp)
                return -1;
            cnt++;
            temp = i;
        }
    }
    if (t.get(i) - t.get(i - 1) > d)
        return -1;
    return cnt + 1;
}