LeetCode 838 - Push Dominoes


https://leetcode.com/problems/push-dominoes/description/
There are N dominoes in a line, and we place each domino vertically upright.
In the beginning, we simultaneously push some of the dominoes either to the left or to the right.
After each second, each domino that is falling to the left pushes the adjacent domino on the left.
Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.
When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.
For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.
Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.
Return a string representing the final state. 
Example 1:
Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
Example 2:
Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.
Note:
  1. 0 <= N <= 10^5
  2. String dominoes contains only 'L', 'R' and '.'

Approach #1: Adjacent Symbols
Between every group of vertical dominoes ('.'), we have up to two non-vertical dominoes bordering this group. Since additional dominoes outside this group do not affect the outcome, we can analyze these situations individually: there are 9 of them (as the border could be empty). Actually, if we border the dominoes by 'L' and 'R', there are only 4 cases. We'll write new letters between these symbols depending on each case.
Algorithm
Continuing our explanation, we analyze cases:
  • If we have say "A....B", where A = B, then we should write "AAAAAA".
  • If we have "R....L", then we will write "RRRLLL", or "RRR.LLL" if we have an odd number of dots. If the initial symbols are at positions i and j, we can check our distance k-i and j-k to decide at position k whether to write 'L', 'R', or '.'.
  • (If we have "L....R" we don't do anything. We can skip this case.)
    public String pushDominoes(String dominoes) {
        int N = dominoes.length();
        int[] indexes = new int[N+2];
        char[] symbols = new char[N+2];
        int len = 1;
        indexes[0] = -1;
        symbols[0] = 'L';

        for (int i = 0; i < N; ++i)
            if (dominoes.charAt(i) != '.') {
                indexes[len] = i;
                symbols[len++] = dominoes.charAt(i);
            }

        indexes[len] = N;
        symbols[len++] = 'R';

        char[] ans = dominoes.toCharArray();
        for (int index = 0; index < len - 1; ++index) {
            int i = indexes[index], j = indexes[index+1];
            char x = symbols[index], y = symbols[index+1];
            char write;
            if (x == y) {
                for (int k = i+1; k < j; ++k)
                    ans[k] = x;
            } else if (x > y) { // RL
                for (int k = i+1; k < j; ++k)
                    ans[k] = k-i == j-k ? '.' : k-i < j-k ? 'R' : 'L';
            }
        }

        return String.valueOf(ans);
    }

法2 计算受力，走两遍
Approach #2: Calculate Force
We can calculate the net force applied on every domino. The forces we care about are how close a domino is to a leftward 'R', and to a rightward 'L': the closer we are, the stronger the force.
Algorithm
Scanning from left to right, our force decays by 1 every iteration, and resets to N if we meet an 'R', so that force[i] is higher (than force[j]) if and only if dominoes[i] is closer (looking leftward) to 'R' (than dominoes[j]).
Similarly, scanning from right to left, we can find the force going rightward (closeness to 'L').
For some domino answer[i], if the forces are equal, then the answer is '.'. Otherwise, the answer is implied by whichever force is stronger.
    public String pushDominoes(String S) {
        char[] A = S.toCharArray();
        int N = A.length;
        int[] forces = new int[N];

        int force = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] == 'R') force = N;
            else if (A[i] == 'L') force = 0;
            else force = Math.max(force - 1, 0);
            forces[i] += force;
        }

        force = 0;
        for (int i = N-1; i >= 0; --i) {
            if (A[i] == 'L') force = N;
            else if (A[i] == 'R') force = 0;
            else force = Math.max(force - 1, 0);
            forces[i] -= force;
        }

        StringBuilder ans = new StringBuilder();
        for (int f: forces)
            ans.append(f > 0 ? 'R' : f < 0 ? 'L' : 'V');
        return ans.toString();
    }
X.
http://storypku.com/2018/06/leetcode-question-838-push-dominoes/
https://www.cnblogs.com/seyjs/p/9071067.html
本题题目中有一点要求很关键，“we will consider that a falling domino expends no additional force to a falling or already fallen domino.”，正好对应题目中的例子2，要好好理解一下。因为输入的最大dominoes是10^5,所以要考虑性能问题。dominoes有三种状态:'R','L','.'。在最终状态里面，R和L是不会变的，只有'.'的状态可能会变成三种状态的任意一种。我的思路是把所有连续的'.'当做一个子序列，然后判断这个子序列左边和右边的dominoes是R还是L，这里分这么几种情况：
a.左右的dominoes方向相同，那么子序列所有的'.'的方向和左右方向相同；
b.左边的dominoes向右，右边的dominoes向左，如下图，那么要考虑子序列长度是奇偶性来决定最中间的'.'的取值。如下图，
c.子序列出现要头尾要单独考虑；
d.左边的dominoes向左，右边的dominoes向右，那么子序列所有的'.'的方向保持不变，还是为'.'；
https://buptwc.com/2018/05/22/Leetcode-838-Push-Dominoes/
    def pushDominoes(self, dominoes):
        """
        :type dominoes: str
        :rtype: str
        """
        res = ''
        i = 0
        # 上一个出现的关键点用last表示，初始为None，处理左边界情况
        last = None
        while i < len(dominoes):
            j = i
            # 遍历到'.'就不管，一直到找到一个'R或L'为止
            while j+1 < len(dominoes) and dominoes[j] == '.': j += 1 
            # 找到L的情况
            if dominoes[j] == 'L':
                if last == 'R':
                    res += (j-i)/2 * 'R' + (j-i)%2 * '.' + (j-i)/2 * 'L' + 'L'
                else:
                    res += 'L' * (j-i+1)
                last = 'L'
            # 找到R的情况
            elif dominoes[j] == 'R':
                if last == 'R':
                    res += (j-i+1) * 'R'
                else:
                    res += (j-i) * '.' + 'R'
                last = 'R'
            i = j + 1
        
        # 出来之后，处理右边界情况
        if last == 'R':
            res += 'R' * (len(dominoes)-len(res))
        else:
            res += '.' * (len(dominoes)-len(res))
        return res

X. Two Pointer
https://blog.csdn.net/fuxuemingzhu/article/details/82714928
如果理解了一个推倒了的牌只能对另一个站着的牌起作用这句话那么基本上就能做出来这个题了，否则是做不出来的。

我们对这个题的理解应该是找出最近的两个被推倒了的牌，然后判断这两个牌是什么样子的即可，不用考虑这个区间以外的牌，因为这两张牌被推倒了，而这个区间外的其他牌不会对推倒了的牌起作用。所以使用双指针的方式解决。

所以在两个被推倒了的区间里：

'R......R' => 'RRRRRRRR'
'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
'L......R' => 'L......R'
'L......L' => 'LLLLLLLL'
1
2
3
4
使用双指针即可解决掉。
https://leetcode.com/problems/push-dominoes/discuss/132332/C++JavaPython-Two-Pointers
Whether be pushed or not, depend on the shortest distance to 'L' and 'R'.
Also the direction matters.
Base on this idea, you can do the same thing inspired by this problem.
https://leetcode.com/problems/shortest-distance-to-a-character/discuss/125788/
Here is another idea that focus on 'L' and 'R'.
'R......R' => 'RRRRRRRR'
'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
'L......R' => 'L......R'
'L......L' => 'LLLLLLLL'
    public String pushDominoes(String d) {
        d = 'L' + d + 'R';
        StringBuilder res = new StringBuilder();
        for (int i = 0, j = 1; j < d.length(); ++j) {
            if (d.charAt(j) == '.') continue;
            int middle = j - i - 1;
            if (i > 0) res.append(d.charAt(i));
            if (d.charAt(i) == d.charAt(j))
                for (int k = 0; k < middle; k++) res.append(d.charAt(i));
            else if (d.charAt(i) == 'L' && d.charAt(j) == 'R')
                for (int k = 0; k < middle; k++) res.append('.');
            else {
                for (int k = 0; k < middle / 2; k++) res.append('R');
                if (middle % 2 == 1) res.append('.');
                for (int k = 0; k < middle / 2; k++) res.append('L');
            }
            i = j;
        }
        return res.toString();
    } 
https://leetcode.com/problems/push-dominoes/discuss/132482/Java-one-pass-in-place-13ms
 public String pushDominoes(String dominoes) {
        char[] a = dominoes.toCharArray();
        int L = -1, R = -1;//positions of last seen L and R
        for (int i = 0; i <= dominoes.length(); i++)
            if (i == a.length || a[i] == 'R') {
                if (R > L)//R..R, turn all to R
                    while (R < i)
                        a[R++] = 'R';
                R = i;
            } else if (a[i] == 'L')
                if (L > R || (R == -1 && L == -1))//L..L, turn all to L
                    while (++L < i)
                        a[L] = 'L';
                else { //R...L
                    L = i;
                    int lo = R + 1, hi = L - 1;
                    while (lo < hi) { //one in the middle stays '.'
                        a[lo++] = 'R';
                        a[hi--] = 'L';
                    }
                }
        return new String(a);
    }

  public String pushDominoes(String input) {
    char[] dominoes = input.toCharArray();
    ArrayDeque<Character> stack = new ArrayDeque<>();

    List<Character> result = new ArrayList<>(dominoes.length);

    for (int i = 0; i < dominoes.length; i++) {
      // improve: save space, store index in the stack not element value
      Character ch = dominoes[i];
      if (ch == '.') {
        stack.add(ch);
      } else if (ch == 'R') {
        // ..R or R or R ... (R)
        // .. L .. R already handled L
        if (!stack.isEmpty()) {
          if (stack.peekFirst() == 'R') {
            for (int k = 0; k < stack.size(); k++) {
              result.add('R');
            }
            stack.clear();
          } else {
            while (!stack.isEmpty()) {
              result.add(stack.removeFirst());
            }
          }
        }
        stack.add(ch);
      } else {
        // ch is L
        // case in stack: ...L or R .. L or L
        // LL or L..L not exist, first L already handled
        if (!stack.isEmpty()) {
          if (stack.peekFirst() == '.') {
            for (int k = 0; k < stack.size(); k++) {
              result.add('L');
            }
            stack.clear();
          } else {
            // case R .. L R ... L

            int size = stack.size() - 1;
            result.add('R');

            for (int k = 0; k < size / 2; k++) {
              result.add('R');
            }
            if (size % 2 == 1) {
              result.add('.');
            }
            for (int k = 0; k < size / 2; k++) {
              result.add('L');
            }

            stack.clear();
          }
        }

        // add ch
        result.add('L');
      }

    }

    if (!stack.isEmpty()) {
      // remaining in stack: .... or R ..
      if (stack.peekFirst() == '.') {
        for (int k = 0; k < stack.size(); k++) {
          result.add('.');
        }
      } else {
        for (int k = 0; k < stack.size(); k++) {
          result.add('R');
        }
      }
    }
    return result.stream().map(String::valueOf).collect(Collectors.joining());

  }

https://www.acwing.com/solution/LeetCode/content/757/
遍历一次字符串，如果当前字符是’.’，那么跳过，如果当前字符是’L’，判断上一次字符last是什么，如果last是’L’，那么就把last到当前字符位置的字符全部赋值为’L’，如果last是’R’，那么前面一半位置赋值为’R’,后面一半位置赋值为’L’，中间赋值为’.’，最后更新last为当前的字符。当前字符是’R’时，如果last是’R’,那么把last到当前字符位置全部赋值为’R’, 如果last是’L’，那么则不做处理（因为last向左倒，当前向右倒），最后更新last的字符和位置。

时间复杂度分析：需要扫描一遍数组，复杂度为O(n)O(n)

X. BFS, Queue
https://leetcode.com/problems/push-dominoes/discuss/132929/Naive-BFS-Easy-to-understand-and-could-be-used-as-first-solution
    public String pushDominoes(String dominoes) {
        char[] arr = new char[dominoes.length()];
        int[] left = new int[dominoes.length()];
        int[] right = new int[dominoes.length()];
        Queue<Integer> leftQ = new LinkedList<>();
        Queue<Integer> rightQ = new LinkedList<>();
        Arrays.fill(left, Integer.MAX_VALUE);
        Arrays.fill(right, Integer.MAX_VALUE);
        for (int i = 0; i < dominoes.length(); i++) {
            if (dominoes.charAt(i) == 'L') {
                leftQ.offer(i);
                left[i] = 0;
            }
            if (dominoes.charAt(i) == 'R') {
                rightQ.offer(i);
                right[i] = 0;
            }
        }
        int step = 0;
        while (leftQ.size() > 0 || rightQ.size() > 0) {
            step++;
            int leftSize = leftQ.size();
            while (leftSize > 0) {
                leftSize--;
                int pos = leftQ.poll();
                if (pos > 0 && left[pos - 1] == Integer.MAX_VALUE && dominoes.charAt(pos - 1) != 'R') {
                    leftQ.offer(pos - 1);
                    left[pos - 1] = step;
                }
            }
            int rightSize = rightQ.size();
            while (rightSize > 0) {
                rightSize--;
                int pos = rightQ.poll();
                if (pos + 1< dominoes.length() && right[pos + 1] == Integer.MAX_VALUE && dominoes.charAt(pos + 1) != 'L') {
                    rightQ.offer(pos + 1);
                    right[pos + 1] = step;
                }
            }
        }
        for (int i = 0; i < dominoes.length(); i++) {
            if (left[i] - right[i] == 0) {
                arr[i] = '.';
            }
            else if (left[i] - right[i] > 0) {
                arr[i] = 'R';
            }
            else {
                arr[i] = 'L';
            }
        }
        return new String(arr);
    }
at
Labels: , , , , , ,

LeetCode 837 - New 21 Game


https://leetcode.com/problems/new-21-game/description/
Alice plays the following game, loosely based on the card game "21".
Alice starts with 0 points, and draws numbers while she has less than K points.  During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer.  Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets K or more points.  What is the probability that she has N or less points?
Example 1:
Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation:  Alice gets a single card, then stops.
Example 2:
Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.
Example 3:
Input: N = 21, K = 17, W = 10
Output: 0.73278
Note:
  1. 0 <= K <= N <= 10000
  2. 1 <= W <= 10000
  3. Answers will be accepted as correct if they are within 10^-5 of the correct answer.
  4. The judging time limit has been reduced for this question.
http://www.programmersought.com/article/575237977/
Using dynamic programming, dp[i] represents the probability of getting the number of points i, and will continue to fetch only if the current total number of points is less than K. Then the state transition equation can be written as:
  1. wheni <= KTime,Dp[i] = (the sum of the first W dp) / W; (climbing the stairs to get the probability that the total number of stairs is i)
  2. whenK < i < K + WWhen, then the range of points in the previous time is[i - W, K - 1]. Our dp array represents the probability of getting the point i, sodp[i]=(dp[K-1]+dp[K-2]+…+dp[i-W])/W(You can select one of the [1, W] numbers from the previous basis)
  3. When i>=K+W, this case should not exist anyway, so dp[i]=0.
https://leetcode.com/problems/new-21-game/discuss/228406/Logical-Thinking
point 0 initially
while (point < K) {
    draw w  from [1, W] randomly 
    point += w
}
probability(point <= N) ?
Let's observe that
point total range [0, K + W - 1]
we define probability[i] as probability to get i points
since all start with point 0 => probability[0] = 1
Probability transition:
Before we reach point `i`, we draw `w`, i.e., our last point is `i - w` 

probability to get i points = sum(probability to get i - w points * 1 / W) for w can be any of [1, W]
where 0 <= i - w < K
target probability = sum of prabability to get points [K, N]
Note
If K = 10, W = 10
draw 1, then 9, probability is P(1) * P(9) = 0.1 * 0.1 = 0.01
draw 10, probability is P(10) = 0.1.
(1, 9) and (10) can't be simply regarded as combination candidates for they don't share the same probability.
    public double new21Game(int N, int K, int W) {
        // Corner cases.
        if (K == 0) return 1;
        
        int maxPoint = K + W - 1;
        // probability[i] is probability of getting point i.
        double[] probability = new double[maxPoint + 1];
        
        probability[0] = 1;
        for (int i = 1; i <= maxPoint; i++) {
            for (int w = 1; w <= W; w++) {
                if (i - w >= 0 && i - w < K)
                    probability[i] += probability[i - w] * 1 / W;
            }
        }
        
        double targetProbability = 0; // Probability of N or less points.
        for (int i = K; i <= N; i++) {
            targetProbability += probability[i];
        }
        
        return targetProbability;
    }
https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N)
The same problems as "Climbing Stairs".
Explanation:
In a word,
dp[i]: probability of get points i
dp[i] = sum(last W dp values) / W
To get Wsum = sum(last W dp values), we can maintain a sliding window with size at most K.
    public double new21Game(int N, int K, int W) {
        if (K == 0 || N >= K + W) return 1;
        double dp[] = new double[N + 1],  Wsum = 1, res = 0;
        dp[0] = 1;
        for (int i = 1; i <= N; ++i) {
            dp[i] = Wsum / W;
            if (i < K) Wsum += dp[i]; else res += dp[i];
            if (i - W >= 0) Wsum -= dp[i - W];
        }
        return res;
    }
https://buptwc.com/2018/05/22/Leetcode-837-New-21-Game/
使用动态规划，dp[i]表示点数和为i的概率，那么最后结果应该是dp[k]+dp[k+1]+…+dp[n]
其中，dp[i]又应该为前w个的dp的平均值
例如W=10，那么dp[20] = 1/10 * (dp[10]+dp[11]+…+dp[19])

def new21Game(N, K, W):
    if K == 0: return 1
    dp = [1.0] + [0.0] * N
    # 用Wsum 记录前w个dp之和
    Wsum = 1.0000
    for i in range(1, N + 1):
        dp[i] = Wsum / W
        if i < K: Wsum += dp[i]
        # 假设K = 15，那么上面的例子d[20] = 1/10 * (dp[10]+...+dp[14]),因为拿到15之后就不能拿了，所以不存在从15拿5拿到20的情况
        if 0 <= i - W < K: Wsum -= dp[i - W]
    return sum(dp[K:])
https://www.acwing.com/solution/LeetCode/content/925/
设 f(i)f(i) 表示得到 ii 点分数的概率。
初始时 f(0)=1f(0)=1，其余为 00。转移时，枚举能从那些值得到 ii，即 j∈[i−W,i−1]j∈[i−W,i−1] 且 j>=0,j<Kj>=0,j<K，f(i)=f(i)+f(j)Wf(i)=f(i)+f(j)W。
最终答案为 f(K)+f(K+1)+⋯+f(N)f(K)+f(K+1)+⋯+f(N)。
如果暴力枚举转移会超时，需要一个前缀和 s(i)s(i) 来维护 f(0)+f(1)+⋯+f(i)f(0)+f(1)+⋯+f(i) 的值，这样转移只需要 O(1)O(1) 的时间。
时间复杂度
状态数 nn 个，优化转移只需要 O(1)O(1) 的时间，故总时间复杂度为 O(n)O(n)。


https://www.cnblogs.com/seyjs/p/9076034.html
这个题目有点像爬楼梯问题，只不过楼梯问题要求的计算多少种爬的方式，但是本题是计算概率。因为点数超过或者等于K后就不允许再增加新的点数了，因此我们可以确定最终Alice拥有的点数的区间是[K,K-1+W]，下限等于K很好理解，Alice最后一次抽取点数前可能拥有的点数最大值是K-1，最后一次抽取的点数最大值是W,因此上限就是K-1+W。和爬楼梯类似，恰好获得点数n的概率dp[n] = sum(dp[n-w]/w + dp[n-w+1]/w + .... dp[n-1]/w)。因为获取任意一个点数的概率都是1/W，所以上面的公式中每个dp都要除以W。但是题目约定了一个K值，在n > k + 1的情况下，dp[n]是无法通过dp[n-1]得到，需要修正公式： dp[n] = sum(dp[n-w]/w + dp[n-w+1]/w + .... dp[K-1]/w)。最后，点数小于或者等于N的概率就是 sum(dp[K:N + 1])

https://blog.csdn.net/fuxuemingzhu/article/details/83615241
类似爬楼梯的问题，每次可以跨[1,W]个楼梯，当一共爬了K个和以上的台阶时停止，问这个时候总台阶数<=N的概率。

使用动态规划，dp[i]表示得到点数i的概率，只有当现在的总点数少于K的时候，才会继续取数。那么状态转移方程可以写成：

当i <= K时，dp[i] = （前W个dp的和）/ W；(爬楼梯得到总楼梯数为i的概率）
当K < i < K + W时，那么在这次的前一次的点数范围是[i - W, K - 1]。我们的dp数组表示的是得到点i的概率，所以dp[i]=(dp[K-1]+dp[K-2]+…+dp[i-W])/W.（可以从前一次的基础的上选[1,W]个数字中的一个）
当i>=K+W时，这种情况下无论如何不都应该存在的，所以dp[i]=0.


https://leetcode.com/problems/new-21-game/discuss/132358/Java-O(K-+-W)-DP-solution-with-explanation

Firstly I came up with a basic DP solution which cost O((K + W) * W) time and it runs TLE:
class Solution {
    public double new21Game(int N, int K, int W) {
        if (K == 0) {
            return 1;
        }
        int max = K + W - 1;
        double[] dp = new double[max + 1];
        dp[0] = 1;
        for (int i = 1; i <= max; i++) {
            for (int j = 1; j <= W; j++) {
                if (i - j >= 0 && i - j < K) {
                    dp[i] += dp[i - j] / W;
                }
            }
        }
        double result = 0;
        for (int i = K; i <= N; i++) {
            result += dp[i];
        }
        return result;
    }
}
Then I realize that the transition equation dp[i] = (dp[i - W] + dp[i - W + 1] + ... + dp[i - 1]) / W could be simplified to dp[i] = (sum[i - 1] - sum[i - W - 1]) / W.
Furthermore, if we use dp[i] to directly represent the sum[i], we can get dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - W - 1]) / W. This equation takes us to the final O(K + W) solution. Just take care with the beginning and the end of the array.
    public double new21Game(int N, int K, int W) {
        if (K == 0) {
            return 1;
        }
        int max = K + W - 1;
        double[] dp = new double[max + 1];
        dp[0] = 1;
        for (int i = 1; i <= max; i++) {
            dp[i] = dp[i - 1];
            if (i <= W) {
                dp[i] += dp[i - 1] / W;
            } else {
                dp[i] += (dp[i - 1] - dp[i - W - 1]) / W;
            }
            if (i > K) {
                dp[i] -= (dp[i - 1] - dp[K - 1]) / W;
            }
        }
        return dp[N] - dp[K - 1];
    }

https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP
In a word,
dp[i]: probability of get points i
dp[i] = sum(last W dp values) / W
    public double new21Game(int N, int K, int W) {
        if (K == 0 || N >= K + W) return 1;
        double dp[] = new double[N + 1],  Wsum = 1, res = 0;
        dp[0] = 1;
        for (int i = 1; i <= N; ++i) {
            dp[i] = Wsum / W;
            if (i < K) Wsum += dp[i]; else res += dp[i];
            if (i - W >= 0) Wsum -= dp[i - W];
        }
        return res;
    }


It is clear that the probability that Alice wins the game is only related to how many points x she starts the next draw with, so we can try to formulate an answer in terms of x.
Algorithm
Let f(x) be the answer when we already have x points. Clearly, f(x) = 1.0 when K <= x <= N, and f(x) = 0.0 when x > N.
We can write a recursion, f(x) = \frac{1}{W}\big( \sum_{i=1}^W f(x+i) \big).
With naive dynamic programming, this leads to a O(K * W + (N-K)) solution: for each state k < K in decreasing order, we'll use the recursion to calculate f(k), doing O(W) work each time. This is not efficient enough.
However, the sums for f(x) and f(x-1) are related: namely, f(x) - f(x-1) = \frac{1}{W} \big( f(x+W) - f(x) \big). This allows us to calculate f(k-1) from f(k) in O(1) time, by maintaining the numerator S = \sum_{i=1}^W f(x+i).
Note that we can reduce the time complexity to O(\max(K, W)) and the space complexity to O(W) by only keeping track of the last W values of dp, but it isn't required.

    public double new21Game(int N, int K, int W) {
        double[] dp = new double[N + W + 1];
        for (int k = K; k <= N; ++k)
            dp[k] = 1.0;

        double S = Math.min(N - K + 1, W);
        for (int k = K - 1; k >= 0; --k) {
            dp[k] = S / W;
            S += dp[k] - dp[k + W];
        }
        return dp[0];
    }

https://blog.csdn.net/qq_20141867/article/details/81261711
    def new21Game(self, N, K, W):
        """
        :type N: int
        :type K: int
        :type W: int
        :rtype: float
        """
        if K == 0: return 1
        dp = [1.0] + [0.0] * N
        # Wsum表示(前W个dp之和)/W
        Wsum = 1.0000
        for i in range(1, N + 1):
            dp[i] = Wsum / W
            # 因为当i>=K时，不能再取数，因此后面的概率不能累加
            if i < K: Wsum += dp[i]
            # 因为只需要计算前w个dp之和，所以当i>=W时，减去最前面的dp。
            if 0 <= i - W < K: Wsum -= dp[i - W]
        return sum(dp[K:])

X. https://github.com/WuLC/LeetCode/blob/master/Algorithm/Python/837.%20New%2021%20Game.py
# recursive with cache, TLE
class Solution(object):     
    def new21Game(self, N, K, W):
        """
        :type N: int
        :type K: int
        :type W: int
        :rtype: float
        """
        self.cache = {}
        base = 1.0/W
        def helper(curr, N, K, W):
            if curr > N:
                return 0
            if K <= curr <= N:
                return 1
            if curr not in self.cache:
                prob = 0
                for i in xrange(1, W+1):
                    if curr+i > N:
                        break
                    if curr+i not in self.cache:
                        self.cache[curr+i] = helper(curr+i, N, K, W)
                    prob += base*self.cache[curr+i]
                self.cache[curr] = prob
            return self.cache[curr]
        return helper(0, N, K, W)

at
Labels: , , , , ,
Subscribe to: Posts (Atom)

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • DropBox Interview Misc
    https://paper.dropbox.com/doc/Interview-Notes-Dropbox-wl7npLjRBjrAKA5AOBsaM Behavioural https://www.paysa.com/blog/2017/04/05/what-to...
  • Minimum area of a square enclosing given set of points
    Problem solving with programming: Minimum area of a square enclosing given set of points Given a set of coordinates in a two dimensional ...
  • HackerRank: N Puzzle
    HackerRank: N Puzzle N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to ...
  • Buttercola: LinkedIn: Add Interval
    Buttercola: LinkedIn: Add Interval http://needjobasap.blogspot.com/2015/05/l-question-get-interval-range.html public interface Interva...
  • Hilbert Curve - Airbnb
    airbnb面试题汇总 Hilbert Curve Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步 int hilbertCurve(...