文章目錄

• 剪繩子 I
• • • 題目描述
    • 思路 && 代碼
    • • • 1. 動態(tài)規(guī)劃 O($n^2$)、O(n)
        • 2. 最優(yōu)解：數(shù)學方法 O(n)、O(1)
    • 二刷
• 剪繩子 II
• • • 題目描述
    • 思路 && 代碼
    • 二刷

剪繩子 I

題目描述

• 還是比較偏數(shù)學的一道題，通過獲取結論來獲得最優(yōu)解
  

思路 && 代碼

1. 動態(tài)規(guī)劃 O($n^2$)、O(n)

• dp[i]：長度為 i 的繩子，可達到的最大值
• 狀態(tài)轉移方程：以之前的值，循環(huán)組合，找出可取的最大值

class Solution {public int cuttingRope(int n) {if(n <= 3) {return n - 1;} int[] dp = new int[n + 1];// 1. 初始化dp[1] = 1;dp[2] = 2;dp[3] = 3;for(int i = 4; i <= n; i++) {int max = 0;for (int j = 1; j <= i / 2; j++) {// 2. 狀態(tài)轉移方程max = Math.max(max, dp[j] * dp[i - j]);}dp[i] = max;}return dp[n];} }

2. 最優(yōu)解：數(shù)學方法 O(n)、O(1)

• 見注釋的正確性證明
• 主要做法就是循環(huán)地切出3，直到所剩值不大于4為止（ n == 4 時候，直接用是最好的，因為 x * 4 == x* 2 * 2 > x * 3 * 1）

class Solution {public int cuttingRope(int n) {// 數(shù)學方法：O(n) & O(1)if(n < 4) {return n - 1;}int res = 1;// 循環(huán)切除3while(n > 4) {res *= 3;n -= 3;}// 最后乘一次 1 or 2 or 3 or 4return res * n;} } /** 正確性證明（參考評論區(qū)大佬）* 1. 任何大于1的數(shù)都可由 2 & 3 組成（偶數(shù)可2累加，奇數(shù)就是前一個偶數(shù)加一次3）* 2. 2 * 2 == 1 * 4 ，且 2 * 3 > 1 * 5，因此拆成2 & 3得到積最大* 3. 因為 2 * 2 * 2 < 3 * 3，因此拆成 3 性價比最高 */

二刷

• 結論題，記住循環(huán)切3就行
• 注意邊界，n < 4 時直接取 n - 1

class Solution {public int cuttingRope(int n) {if(n < 4) {return n - 1;}int ans = 1;while(n > 4) {n -= 3;ans *= 3;}return n * ans;} }

剪繩子 II

題目描述

• 相較于1，多了一個取模操作
  

思路 && 代碼

class Solution {public int cuttingRope(int n) {if(n < 4) {return n - 1;}long res = 1L;while(n > 4) {res *= 3;res %= 1000000007;n -= 3;}return (int)(res * n % 1000000007);} }

二刷

• 注意涉及取模，直接用Long，防止溢出

class Solution {public int cuttingRope(int n) {if(n < 4) {return n - 1;}long ans = 1L;while(n > 4) {ans *= 3;ans %= 1000000007;n -= 3;}return (int)(ans * n % 1000000007);} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 14. 剪绳子 I II（Java、动态规划、偏数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。