LeetCode-343. 整數拆分 - 題解分析

来源:https://www.cnblogs.com/GarrettWale/archive/2023/01/25/17067269.html
-Advertisement-
Play Games

題目來源 343. 整數拆分 題目詳情 給定一個正整數 n ,將其拆分為 k 個 正整數 的和( k >= 2 ),並使這些整數的乘積最大化。 返回 你可以獲得的最大乘積 。 示例 1: 輸入: n = 2 輸出: 1 解釋: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 輸入: n = ...


題目來源

343. 整數拆分

題目詳情

給定一個正整數 n ,將其拆分為 k正整數 的和( k >= 2 ),並使這些整數的乘積最大化。

返回 你可以獲得的最大乘積 。

示例 1:

輸入: n = 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

輸入: n = 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

  • 2 <= n <= 58

題解分析

本題整數拆分的核心問題是如何定義狀態方程的轉移。狀態方程的定義是比較簡單的,dp[i]就表示i拆分後可以得到的最大乘積。對於dp[i]的狀態轉移來說,需要考慮以下兩種情況:

  • i可以拆分為j和i-j,i-j無需再次拆分,此時的乘積為:j * (i - j)
  • i可以拆分為j和i-j,將i-j再次拆分,此時的乘積為:j * dp[i - j]

為了求得最大乘積,需要從1開始遍歷上述的j,在遍歷的過程中不斷更新dp[i]為最大值。

結果只需要返回dp[n]即可,也就是將n進行拆分後的最優結果。

java實現

class Solution {
    public int integerBreak(int n) {
        // dp[i] = max(j * (i - j), j * dp[i-j])
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;// 不可再分
        for (int i=2; i<=n; i++) {
            dp[i] = 0;
            for (int j = 1; j<i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i-j]));
            }
        }
        return dp[n];
    }
}

參考

官方題解-整數拆分

Either Excellent or Rusty
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 測試網站是本人學校,費話不多說下麵開始 首先直接導庫,過程中需要時間戳,rsa加密 import requests import re import time from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_v1_5 ...
  • 2023-01-24 一、NoSQL資料庫 1、NoSQL資料庫的簡介 NoSQL(NoSQL=Not Only SQL),即“不僅僅是SQL”,泛指非關係型的資料庫。NosQL不依賴業務邏輯方式存儲,而以簡單的key-value模式存儲。因此大大的增加了資料庫的擴展能力。 (1)不遵循SQL標準 ...
  • 1、首先是adb版本需要新的,老的adb不支持無線連接,如:“adb pair 192.168.3.x:xxxxx”不支持pair這個參數,這個參數表示驗證配對碼!!!新的adb才支持。 無法識別pair參數 2、支持無線調試的手機需要和用於調試的電腦在同一個區域網下。 3、通過adb連接: 【1】 ...
  • JavaScript 中有兩種類型轉換:隱式類型轉換和顯式類型轉換。 隱式類型轉換指 JavaScript 在運行時自動將一種類型轉換為另一種類型。例如,在數學運算中,JavaScript 會將字元串轉換為數字。 顯式類型轉換指在代碼中使用內置函數或全局對象將一種類型顯式地轉換為另一種類型。例如,使 ...
  • JavaScript 中有多種方法可以實現數組去重,下麵是幾種常用的方法: 1、使用 Set 去重:Set 數據結構中不能有重覆元素,可以將數組轉成 Set 類型,再轉回數組。 let arr = [1,2,3,4,5,6,2,3,4]; let uniqueArr = [...new Set(ar ...
  • 前言 為何要學習代碼?為何要學習這個代碼?怎麼學習這個代碼?可不可以學習這個代碼? 能做什麼,有什麼目標? ​ 基本的手機應用、簡單的PC游戲應用、大數據平臺;目標是以愛好為基準做一些游戲和程式; 與Python優缺幾何? ​ 入門難度有區別;一個更面向程式員群體一個則面向費程式員群體;各有優缺; ...
  • 本文作者通過分析微服務的常見優點能解決的問題,提出如何使用單體應用來緩解這些問題,最終指出採用微服務還是單體架構要根據團隊實際情況,而不是為了微服務而微服務。作者最後給出建議,中小團隊和新型團隊,建議採用單體架構,大中型團隊,可以採用微服務架構,但要充分權衡。 在 Web 軟體架構方面,微服務... ...
  • 這篇文章主要關註健康檢測相關的內容,包括服務提供方可能得狀態以及撞見間轉化、什麼是可用率、檢測程式的部署方式等。 ...
一周排行
    -Advertisement-
    Play Games
  • 一:背景 1. 講故事 年前遇到了好幾例托管堆被損壞的案例,有些運氣好一些,從被破壞的托管堆記憶體現場能觀測出大概是什麼問題,但更多的情況下是無法做出準確判斷的,原因就在於生成的dump是第二現場,借用之前文章的一張圖,大家可以理解一下。 為了幫助更多受此問題困擾的朋友,這篇來整理一下如何 快狠準 的 ...
  • 前言 .NET6 開始,.NET Croe API 項目取消了 Startup.cs 文件,在 Program.cs 文件的 Main 函數中完成服務的註冊和中間件管道的管理。但當我們項目引入更多包的時候,Program.cs 文件也會看起來很臃腫。 而且,我們不只會有一個後端項目,為了方便快速創建 ...
  • 目錄 背景 get 與 post 的區別 所有介面都用 post 請求? 背景 最近在逛知乎的時候發現一個有趣的問題:公司規定所有介面都用 post 請求,這是為什麼? 看到這個問題的時候其實我也挺有感觸的,因為我也曾經這樣問過我自己。在上上一家公司的時候接到一個項目是從零開始搭建一個微服務,當時就 ...
  • *以下內容為本人的學習筆記,如需要轉載,請聲明原文鏈接 微信公眾號「englyf」https://mp.weixin.qq.com/s/2GFLTstDC7w6u3fTJxflNA 本文大概 1685 個字,閱讀需花 6 分鐘內容不多, 但也花了一些精力如要交流, 歡迎關註我然後評論區留言 謝謝你的 ...
  • 在新版本的pandas中,上述代碼會引起警告,建議改成SQLAlchemy connectable(engine/connection),後續代碼將引入這種升級的連接方式。 ...
  • 幾乎所有的高級編程語言都有自己的垃圾回收機制,開發者不需要關註記憶體的申請與釋放,Python 也不例外。Python 官方團隊的文章 https://devguide.python.org/internals/garbage-collector 詳細介紹了 Python 中的垃圾回收演算法,本文是這篇 ...
  • 如果您想查找高於或低於平均值的數字,可以不必計算該平均值,就能查看更高或更低的值。通過Java應用程式,可以自動突出顯示這些數字。除了快速突出顯示高於或低於平均值的值外,您還可以查看高於或低於的值的個數。現在讓我們看看如何在 Java應用程式中實現此操作。 引入jar包 導入方法1: 手動引入。將  ...
  • 第一種方式:使用{} firstDict = {"name": "wang yuan wai ", "age" : 25} 說明:{}為創建一個空的字典對象 第二種方式:使用fromkeys()方法 second_dict = dict.fromkeys(("name", "age")) #valu ...
  • 在golang中可以使用a := b這種方式將b賦值給a,只有當b能進行深拷貝時a與b才不會互相影響,否則就需要進行更為複雜的深拷貝。 下麵就是Go賦值操作的一個說明: Go語言中所有賦值操作都是值傳遞,如果結構中不含指針,則直接賦值就是深度拷貝;如果結構中含有指針(包括自定義指針,以及切片,map ...
  • 本文結合京東監控埋點場景,對解決樣板代碼的技術選型方案進行分析,給出最終解決方案後,結合理論和實踐進一步展開。通過關註文中的技術分析過程和技術場景,讀者可收穫一種樣板代碼思想過程和解決思路,並對Java編譯器底層有初步瞭解。 ...