資訊專欄INFORMATION COLUMN
摘要：在剪第一刀時(shí)，我們有種選擇，也就是說第一段繩子的可能長(zhǎng)度分別為，。由于遞歸會(huì)有大量的不必要的重復(fù)計(jì)算。子問題的最優(yōu)解存儲(chǔ)在數(shù)組中，數(shù)組中的第個(gè)元素表示把長(zhǎng)度為的繩子剪成若干段后各段長(zhǎng)度乘積的最大值。
剪繩子
給你一根長(zhǎng)度為n的繩子，請(qǐng)把繩子剪成m段 (m和n都是整數(shù)，n>1并且m>1)每段繩子的長(zhǎng)度記為k[0],k[1],...,k[m].請(qǐng)問k[0]k[1]...*k[m]可能的最大乘積是多少？
例如，當(dāng)繩子的長(zhǎng)度為8時(shí)，我們把它剪成長(zhǎng)度分別為2,3,3的三段，此時(shí)得到的最大乘積是18。
思路：
首先定義函數(shù)f(n)為把長(zhǎng)度為n的繩子剪成若干段后各段長(zhǎng)度乘積的最大值。在剪第一刀時(shí)，我們有n-1種選擇，也就是說第一段繩子的可能長(zhǎng)度分別為1,2,3.....，n-1。因此f(n)=max(f(i)*f(n-i))，其中0 這是一個(gè)自上而下的遞歸公式。由于遞歸會(huì)有大量的不必要的重復(fù)計(jì)算。一個(gè)更好的辦法是按照從下而上的順序計(jì)算，也就是說我們先得到f(2),f(3)，再得到f(4),f(5)，直到得到f(n)。 當(dāng)繩子的長(zhǎng)度為2的時(shí)候，只能剪成長(zhǎng)度為1的兩段，所以f(2) = 1，當(dāng)n = 3時(shí)，容易得出f(3) = 2;// 題目的意思是:繩子至少是2米，并且必須最少剪一刀。
function maxAfterCutting(len) {
if(len < 2) {
return 0;
}
if(len === 2) {
return 1;
}
if(len === 3) {
return 2;
}
// 子問題的最優(yōu)解存儲(chǔ)在products數(shù)組中，數(shù)組中的第i個(gè)元素表示把長(zhǎng)度為i的繩子剪成若干段后各段長(zhǎng)度乘積的最大值。
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))
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/107502.html
摘要：貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是類算法的一個(gè)共同點(diǎn)。 貪心算法的基本要素對(duì)于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 1、貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整...
摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法集合字典一遞歸學(xué)習(xí)樹離不開遞歸。先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典 一、遞歸 學(xué)習(xí)樹離不開遞歸。 1.1 介紹 遞歸是一種解決問題的方法，它解決問題的各個(gè)小部分，直到解決最初的大問題。遞歸通常涉及函數(shù)調(diào)用自身。 通俗的解釋：年級(jí)...
閱讀 2989·2023-04-25 21:23
閱讀 3021·2021-09-22 15:24
閱讀 862·2019-08-30 12:55
閱讀 2094·2019-08-29 18:42
閱讀 2606·2019-08-29 16:27
閱讀 943·2019-08-26 17:40
閱讀 2172·2019-08-26 13:29
閱讀 2604·2019-08-26 11:45
