{"id":6750,"date":"2020-05-15T17:17:48","date_gmt":"2020-05-16T00:17:48","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6750"},"modified":"2020-05-16T21:03:05","modified_gmt":"2020-05-17T04:03:05","slug":"leetcode-1444-number-of-ways-of-cutting-a-pizza","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1444-number-of-ways-of-cutting-a-pizza\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1444. Number of Ways of Cutting a Pizza"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1444. Number of Ways of Cutting a Pizza - \u5237\u9898\u627e\u5de5\u4f5c EP326\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/q2Wh5v___r8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given a rectangular pizza represented as a&nbsp;<code>rows x cols<\/code>&nbsp;matrix containing the following characters:&nbsp;<code>'A'<\/code>&nbsp;(an apple) and&nbsp;<code>'.'<\/code>&nbsp;(empty cell) and given the integer&nbsp;<code>k<\/code>. You have to cut the pizza into&nbsp;<code>k<\/code>&nbsp;pieces using&nbsp;<code>k-1<\/code>&nbsp;cuts.&nbsp;<\/p>\n\n\n\n<p>For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.<\/p>\n\n\n\n<p><em>Return the number of ways of cutting the pizza such that each piece contains&nbsp;<strong>at least<\/strong>&nbsp;one apple.&nbsp;<\/em>Since the answer can be a huge number, return this modulo 10^9 + 7.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/04\/23\/ways_to_cut_apple_1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> pizza = [\"A..\",\"AAA\",\"...\"], k = 3\n<strong>Output:<\/strong> 3 \n<strong>Explanation:<\/strong> The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.\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> pizza = [\"A..\",\"AA.\",\"...\"], k = 3\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> pizza = [\"A..\",\"A..\",\"...\"], k = 1\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= rows, cols &lt;= 50<\/code><\/li><li><code>rows ==&nbsp;pizza.length<\/code><\/li><li><code>cols ==&nbsp;pizza[i].length<\/code><\/li><li><code>1 &lt;= k &lt;= 10<\/code><\/li><li><code>pizza<\/code>&nbsp;consists of characters&nbsp;<code>'A'<\/code>&nbsp;and&nbsp;<code>'.'<\/code>&nbsp;only.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326.png\" alt=\"\" class=\"wp-image-6755\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-2.png\" alt=\"\" class=\"wp-image-6756\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-3.png\" alt=\"\" class=\"wp-image-6757\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1444-ep326-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp(n, m, k) := # of ways to cut pizza[n:N][m:M] with k cuts.<\/p>\n\n\n\n<p>dp(n, m, k) = sum(hasApples(n, m, N &#8211; 1, y) * dp(y + 1, n, k &#8211; 1) for y in range(n, M)) + sum(hasApples(n, m, x, M &#8211; 1) * dp(m, x + 1, k &#8211; 1) for x in range(n, M))<\/p>\n\n\n\n<p>Time complexity: O(M*N*(M+N)*K) = O(N^3 * K)<br>Space complexity: O(M*N*K)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int ways(vector<string>& pizza, int K) {\n    constexpr int kMod = 1e9 + 7;\n    const int M = pizza.size();\n    const int N = pizza[0].size();\n    \n    vector<vector<int>> A(M + 1, vector<int>(N + 1));  \n    for (int y = 0; y < M; ++y)\n      for (int x = 0; x < N; ++x)\n        A[y + 1][x + 1] = A[y + 1][x] + A[y][x + 1] + (pizza[y][x] == 'A') - A[y][x];\n    \n    auto hasApples = [&#038;](int x1, int y1, int x2, int y2) {\n      return (A[y2 + 1][x2 + 1] - A[y2 + 1][x1] - A[y1][x2 + 1] + A[y1][x1]) > 0;\n    };\n    \n    vector<vector<vector<int>>> cache(M, vector<vector<int>>(N, vector<int>(K, -1)));\n    \n    \/\/ dp(m, n, k) := # of ways to cut pizza[m:M][n:N] with k cuts.\n    function<int(int, int, int)> dp = [&](int m, int n, int k) -> int {\n      if (k == 0) return hasApples(n, m, N - 1, M - 1);\n      int& ans = cache[m][n][k];\n      if (ans != -1) return ans;      \n      ans = 0;      \n      for (int y = m; y < M - 1; ++y)  \/\/ Cut horizontally.\n        ans = (ans + hasApples(n, m, N - 1, y) * dp(y + 1, n, k - 1)) % kMod;         \n      for (int x = n; x < N - 1; ++x)  \/\/ Cut vertically.\n        ans = (ans + hasApples(n, m, x, M - 1) * dp(m, x + 1, k - 1)) % kMod;\n      return ans;\n    };  \n    return dp(0, 0, K - 1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a rectangular pizza represented as a&nbsp;rows x cols&nbsp;matrix containing the following characters:&nbsp;&#8216;A&#8217;&nbsp;(an apple) and&nbsp;&#8216;.&#8217;&nbsp;(empty cell) and given the integer&nbsp;k. You have to cut the&#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,217,597],"class_list":["post-6750","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-on3k","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6750","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=6750"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6750\/revisions"}],"predecessor-version":[{"id":6760,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6750\/revisions\/6760"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6750"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6750"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6750"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}