{"id":5771,"date":"2019-10-19T21:05:29","date_gmt":"2019-10-20T04:05:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5771"},"modified":"2019-10-19T21:14:45","modified_gmt":"2019-10-20T04:14:45","slug":"leetcode-1230-toss-strange-coins","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1230-toss-strange-coins\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1230. Toss Strange Coins"},"content":{"rendered":"\n<p>You have some coins.&nbsp; The&nbsp;<code>i<\/code>-th&nbsp;coin has a probability&nbsp;<code>prob[i]<\/code>&nbsp;of facing heads when tossed.<\/p>\n\n\n\n<p>Return the probability that the number of coins facing heads equals&nbsp;<code>target<\/code>&nbsp;if you toss every coin exactly once.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> prob = [0.4], target = 1\n<strong>Output:<\/strong> 0.40000\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> prob = [0.5,0.5,0.5,0.5,0.5], target = 0\n<strong>Output:<\/strong> 0.03125\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= prob.length &lt;= 1000<\/code><\/li><li><code>0 &lt;= prob[i] &lt;= 1<\/code><\/li><li><code>0 &lt;= target&nbsp;<\/code><code>&lt;= prob.length<\/code><\/li><li>Answers will be accepted as correct if they are within&nbsp;<code>10^-5<\/code>&nbsp;of the correct answer.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>dp[i][j] := prob of j coins face up after tossing first i coins.<br>dp[i][j] = dp[i-1][j] * (1 &#8211; p[i]) + dp[i-1][j-1] * p[i]<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2) -&gt; O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  double probabilityOfHeads(vector<double>& prob, int target) {\n    const int n = prob.size();\n    vector<double> dp(target + 1);    \n    dp[0] = 1.0;\n    for (int i = 0; i < n; ++i)\n      for (int j = min(i + 1, target); j >= 0; --j)\n        dp[j] = dp[j] * (1 - prob[i]) + (j > 0 ? dp[j - 1] : 0) * prob[i];\n    return dp[target];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>Solution 2: Recursion + Memorization<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  double probabilityOfHeads(vector<double>& prob, int target) {    \n    vector<vector<double>> mem(prob.size() + 1, vector<double>(target + 1, -1)); \n    function<double(int, int)> dp = [&](int n, int k) {\n      if (k > n || k < 0) return 0.0;      \n      if (n == 0) return 1.0;\n      if (mem[n][k] >= 0) return mem[n][k];\n      const double p = prob[n - 1];\n      return mem[n][k] = p * dp(n - 1, k - 1) + (1 - p) * dp(n - 1, k);\n    };    \n    return dp(prob.size(), target);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have some coins.&nbsp; The&nbsp;i-th&nbsp;coin has a probability&nbsp;prob[i]&nbsp;of facing heads when tossed. Return the probability that the number of coins facing heads equals&nbsp;target&nbsp;if you toss&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,498],"class_list":["post-5771","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-on2","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5771","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5771"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5771\/revisions"}],"predecessor-version":[{"id":5774,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5771\/revisions\/5774"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5771"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5771"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5771"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}