{"id":386205,"date":"2024-06-29T06:34:18","date_gmt":"2024-06-29T06:34:18","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=386205"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-06-29T06:34:18","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=386205","title":{"rendered":"LeetCode 956 (Hard). Solution of the day. Tallest Billboard. Swift. DP<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

Description<\/h3>\n

You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.<\/p>\n

You are given a collection of rods that can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.<\/p>\n

Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.<\/p>\n

Example 1<\/strong>:
Input: rods = [1,2,3,6]
Output: 6
Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.<\/p>\n

Example 2<\/strong>:
Input: rods = [1,2,3,4,5,6]
Output: 10
Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.<\/p>\n

Example 3<\/strong>:
Input: rods = [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.<\/p>\n

Constraints<\/strong>:
1 <= rods.length <= 20
1 <= rods[i] <= 1000
sum(rods[i]) <= 5000<\/p>\n

Approach<\/h3>\n

The code uses dynamic programming to solve the problem. It maintains a dictionary dp, where the keys represent the possible height differences between the two billboards, and the values represent the maximum sum of heights achieved for each height difference.<\/p>\n

The code iterates through each rod in the given input rods. For each rod i, it creates a new dictionary cur to store the updated values for dp. Then, it iterates through the existing entries in dp and updates the values in cur based on three cases:<\/p>\n

    \n
  1. \n

    Adding the current rod i to the same height difference: cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])<\/p>\n<\/li>\n

  2. \n

    Keeping the same height difference: cur[sum] = max(dp[sum]!, cur[sum, default: 0])<\/p>\n<\/li>\n

  3. \n

    Subtracting the current rod i from the height difference: cur[sum — i] = max(dp[sum]!, cur[sum — i, default: 0])<\/p>\n<\/li>\n<\/ol>\n

    After iterating through all the rods, the final result is obtained from dp[0], which represents the maximum possible sum of heights for a height difference of 0 (i.e., the two billboards have equal heights).<\/p>\n

    Complexity<\/h3>\n

    Time complexity<\/strong>: O(n * m).<\/p>\n

    Code (Swift)<\/p>\n

    class Solution {     func tallestBillboard(_ rods: [Int]) -> Int {         var dp = [0: 0]          for i in rods {             var cur = [Int: Int]()             for (sum, height) in dp {                 cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])                 cur[sum] = max(dp[sum]!, cur[sum, default: 0])                 cur[sum - i] = max(dp[sum]!, cur[sum - i, default: 0])             }             dp = cur         }          return dp[0, default: 0]     } }<\/code><\/pre>\n
    Sources:\u00a0Github<\/u><\/a><\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n
    <\/div>\n

     \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438      https:\/\/habr.com\/ru\/articles\/743654\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    <\/div>\n
    \n
    \n
    \n
    \n
    Description<\/h3>\n
    You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.<\/p>\n
    You are given a collection of rods that can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.<\/p>\n
    Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.<\/p>\n
    Example 1<\/strong>:
    Input: rods = [1,2,3,6]
    Output: 6
    Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.<\/p>\n
    Example 2<\/strong>:
    Input: rods = [1,2,3,4,5,6]
    Output: 10
    Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.<\/p>\n
    Example 3<\/strong>:
    Input: rods = [1,2]
    Output: 0
    Explanation: The billboard cannot be supported, so we return 0.<\/p>\n
    Constraints<\/strong>:
    1 <= rods.length <= 20
    1 <= rods[i] <= 1000
    sum(rods[i]) <= 5000<\/p>\n
    Approach<\/h3>\n
    The code uses dynamic programming to solve the problem. It maintains a dictionary dp, where the keys represent the possible height differences between the two billboards, and the values represent the maximum sum of heights achieved for each height difference.<\/p>\n
    The code iterates through each rod in the given input rods. For each rod i, it creates a new dictionary cur to store the updated values for dp. Then, it iterates through the existing entries in dp and updates the values in cur based on three cases:<\/p>\n
      \n
    1. \n
      Adding the current rod i to the same height difference: cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])<\/p>\n<\/li>\n
    2. \n
      Keeping the same height difference: cur[sum] = max(dp[sum]!, cur[sum, default: 0])<\/p>\n<\/li>\n
    3. \n
      Subtracting the current rod i from the height difference: cur[sum — i] = max(dp[sum]!, cur[sum — i, default: 0])<\/p>\n<\/li>\n<\/ol>\n
      After iterating through all the rods, the final result is obtained from dp[0], which represents the maximum possible sum of heights for a height difference of 0 (i.e., the two billboards have equal heights).<\/p>\n
      Complexity<\/h3>\n
      Time complexity<\/strong>: O(n * m).<\/p>\n
      Code (Swift)<\/p>\n
      class Solution {     func tallestBillboard(_ rods: [Int]) -> Int {         var dp = [0: 0]          for i in rods {             var cur = [Int: Int]()             for (sum, height) in dp {                 cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])                 cur[sum] = max(dp[sum]!, cur[sum, default: 0])                 cur[sum - i] = max(dp[sum]!, cur[sum - i, default: 0])             }             dp = cur         }          return dp[0, default: 0]     } }<\/code><\/pre>\n
      Sources:\u00a0Github<\/u><\/a><\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n
      <\/div>\n

       \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438        https:\/\/habr.com\/ru\/articles\/743654\/<\/a>
      <\/br><\/br><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-386205","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/386205","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=386205"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/386205\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=386205"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=386205"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=386205"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}