数据结构与算法（动态规划与贪婪算法） --javascript语言描述

30e8336b8229 发布于2019-08-26 11:45 / 2602人阅读

摘要：在剪第一刀时，我们有种选择，也就是说第一段绳子的可能长度分别为，。由于递归会有大量的不必要的重复计算。子问题的最优解存储在数组中，数组中的第个元素表示把长度为的绳子剪成若干段后各段长度乘积的最大值。

剪绳子

给你一根长度为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))

云服务器 GPU云服务器算法与数据结构数据结构与算法算法与数据挖掘数据结构与算法教程

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/107502.html

贪心算法

摘要：贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是类算法的一个共同点。贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 1、贪心选择性质所谓贪心选择性质是指所求问题的整...

missonce 2019-07-30 16:39 评论0 收藏0
JS数据结构与算法_树

摘要：上一篇数据结构与算法集合字典一递归学习树离不开递归。先序遍历的一种应用是打印一个结构化的文档下面的图描绘了先序遍历方法的访问路径后序遍历后序遍历则是先访问节点的后代节点，再访问节点本身。上一篇：JS数据结构与算法_集合&字典一、递归学习树离不开递归。 1.1 介绍递归是一种解决问题的方法，它解决问题的各个小部分，直到解决最初的大问题。递归通常涉及函数调用自身。通俗的解释：年级...

tabalt 2019-08-26 13:35 评论0 收藏0