{"id":6652,"date":"2020-04-20T23:18:20","date_gmt":"2020-04-21T06:18:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6652"},"modified":"2020-04-20T23:20:52","modified_gmt":"2020-04-21T06:20:52","slug":"leetcode-1420-build-array-where-you-can-find-the-maximum-exactly-k-comparisons","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1420-build-array-where-you-can-find-the-maximum-exactly-k-comparisons\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons"},"content":{"rendered":"\n

Given three integers n<\/code>, m<\/code> and k<\/code>. Consider the following algorithm to find the maximum element of an array of positive integers:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

You should build the array arr which has the following properties:<\/p>\n\n\n\n

  • arr<\/code> has exactly n<\/code> integers.<\/li>
  • 1 <= arr[i] <= m<\/code> where (0 <= i < n)<\/code>.<\/li>
  • After applying the mentioned algorithm to arr<\/code>, the value search_cost<\/code> is equal to k<\/code>.<\/li><\/ul>\n\n\n\n

    Return the number of ways<\/em> to build the array arr<\/code> under the mentioned conditions. As the answer may grow large, the answer must be<\/strong> computed modulo 10^9 + 7<\/code>.<\/p>\n\n\n\n

    Example 1:<\/strong><\/p>\n\n\n\n

    Input:<\/strong> n = 2, m = 3, k = 1\nOutput:<\/strong> 6\nExplanation:<\/strong> The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> n = 5, m = 2, k = 3\nOutput:<\/strong> 0\nExplanation:<\/strong> There are no possible arrays that satisify the mentioned conditions.\n<\/pre>\n\n\n\n
    Example 3:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> n = 9, m = 1, k = 1\nOutput:<\/strong> 1\nExplanation:<\/strong> The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]\n<\/pre>\n\n\n\n
    Example 4:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> n = 50, m = 100, k = 25\nOutput:<\/strong> 34549172\nExplanation:<\/strong> Don't forget to compute the answer modulo 1000000007\n<\/pre>\n\n\n\n
    Example 5:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> n = 37, m = 17, k = 7\nOutput:<\/strong> 418930126\n<\/pre>\n\n\n\n
    Constraints:<\/strong><\/p>\n\n\n\n
    • 1 <= n <= 50<\/code><\/li>
    • 1 <= m <= 100<\/code><\/li>
    • 0 <= k <= n<\/code><\/li><\/ul>\n\n\n\n
      Solution: DP<\/strong><\/h2>\n\n\n\n
      dp[n][m][k] := ways to build given n,m,k.<\/p>\n\n\n\n
      dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m
      dp[1][m][1] = m
      dp[n][m][k] = 0 if k < 1 or k > m or k > n<\/p>\n\n\n\n
      Time complexity: O(n*m^2*k)
      Space complexity: O(n*m*k)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nint mem[51][101][51] = {0};\nclass Solution {\npublic:\n  int numOfArrays(int n, int m, int k) {\n    const int kMod = 1e9 + 7;    \n    function dp = [&dp](int n, int m, int k) {\n      if (k < 1 || k > m || k > n) return 0;\n      if (n == 1 && k == 1) return m;\n      if (mem[n][m][k]) return mem[n][m][k];      \n      long ans = 0;\n      for (int i = 1; i <= m; ++i) {\n        ans += dp(n - 1, m, k);\n        ans += dp(n - 1, i - 1, k - 1);\n        ans -= dp(n - 1, i - 1, k);\n        ans = (ans + kMod) % kMod;\n      }\n      return mem[n][m][k] = ans;\n    };    \n    return dp(n, m, k);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      Given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers: You should build the array arr which…<\/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":[8,18,217],"class_list":["post-6652","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-counting","tag-dp","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6652","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=6652"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6652\/revisions"}],"predecessor-version":[{"id":6655,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6652\/revisions\/6655"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6652"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6652"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6652"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}