資訊專欄INFORMATION COLUMN
摘要：在剪第一刀時，我們有種選擇，也就是說第一段繩子的可能長度分別為，。由于遞歸會有大量的不必要的重復計算。子問題的最優解存儲在數組中，數組中的第個元素表示把長度為的繩子剪成若干段后各段長度乘積的最大值。
剪繩子
給你一根長度為n的繩子，請把繩子剪成m段 (m和n都是整數，n>1并且m>1)每段繩子的長度記為k[0],k[1],...,k[m].請問k[0]k[1]...*k[m]可能的最大乘積是多少？
例如，當繩子的長度為8時，我們把它剪成長度分別為2,3,3的三段，此時得到的最大乘積是18。
思路：
首先定義函數f(n)為把長度為n的繩子剪成若干段后各段長度乘積的最大值。在剪第一刀時，我們有n-1種選擇，也就是說第一段繩子的可能長度分別為1,2,3.....，n-1。因此f(n)=max(f(i)*f(n-i))，其中0 這是一個自上而下的遞歸公式。由于遞歸會有大量的不必要的重復計算。一個更好的辦法是按照從下而上的順序計算，也就是說我們先得到f(2),f(3)，再得到f(4),f(5)，直到得到f(n)。 當繩子的長度為2的時候，只能剪成長度為1的兩段，所以f(2) = 1，當n = 3時，容易得出f(3) = 2;// 題目的意思是:繩子至少是2米，并且必須最少剪一刀。
function maxAfterCutting(len) {
if(len < 2) {
return 0;
}
if(len === 2) {
return 1;
}
if(len === 3) {
return 2;
}
// 子問題的最優解存儲在products數組中，數組中的第i個元素表示把長度為i的繩子剪成若干段后各段長度乘積的最大值。
let products = [];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
let max = 0;
for (var i = 4; i <= len; i++) {
max = 0;
for (var j = 1; j <= i/2 ; j++) {
let product = products[j] * products[i-j];
if(max < product) {
max = product;
}
}
products[i] = max;
}
max = products[len];
return max;
}
console.log(maxAfterCutting(8))
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/107502.html
摘要：上一篇數據結構與算法集合字典一遞歸學習樹離不開遞歸。先序遍歷的一種應用是打印一個結構化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節點的后代節點，再訪問節點本身。 上一篇：JS數據結構與算法_集合&字典 一、遞歸 學習樹離不開遞歸。 1.1 介紹 遞歸是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞歸通常涉及函數調用自身。 通俗的解釋：年級...
閱讀 2997·2023-04-25 21:23
閱讀 3037·2021-09-22 15:24
閱讀 866·2019-08-30 12:55
閱讀 2099·2019-08-29 18:42
閱讀 2611·2019-08-29 16:27
閱讀 953·2019-08-26 17:40
閱讀 2185·2019-08-26 13:29
閱讀 2612·2019-08-26 11:45
