专栏首页女程序员的日常_Lin今日算法题-动态规划法

今日算法题-动态规划法

动态规划

定义:通过把原问题分解成多个子问题来解决复杂问题的方法;

解释:动态规划用于解决重叠子问题和最优子结构的问题。

思想:若要解决一个问题,我们需要解其不同部分,再根据子问题的解得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量;一旦某个给定子问题的解已经算出,就将其记忆化存储,以便下次需要同一个子问题解时直接查表。这种方法在重复子问题的数目关于输入的规模呈指数增长时特别有用

整数拆分

题目:给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

以6为例子:

这个问题我们就可以用动态规划法来解决;

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
  let dp = new Array(n+1);
  dp[1] = 1;
  dp[2] = 1;
  for(let i= 3; i <= n ; i++){
    // 从小到大计算出每个dp的值
    dp[i] = 0;
    for(let j = 1; j<= i-j ; j++){  
      // j*(i-j) 不拆分i-j 
      // j*dp[i-j] 继续对i-j进行拆分,
      // dp[i-j]已经在之前的计算中计算过了,不必重复计算
      dp[i] = Math.max(dp[i], j*(i-j), j*dp[i-j])
    }
  }
  return dp[n]
};

当我们不再需要外在的认可来证明自己时

才能获得真正的自由

本文分享自微信公众号 - 女程序员的日常(gh_df41d619fb70),作者:凛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 『ACM-算法-动态规划』初识DP动态规划算法

    一、多阶段决策过程的最优化问题 在现实生活中,有类活 动的过程,由于 它的特殊性,可将过程分成若干个互相阶段。在它的每一阶段都需要作出决策,从而使整个过程达到...

    风骨散人Chiam
  • 动态规划算法

    动态规划过程:每一次决策依赖于当前的状态,即下一状态的产生取决于当前状态。一个决策序列就是在变化的状态中产生的,这种多阶段最优化问题的求解过程就是动态规则过程。...

    YGingko
  • 动态规划算法

    首先,动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。

    麋鹿大哥
  • 【算法】动态规划

    瑞新
  • 动态规划算法-背包问题

    温安适
  • 动态规划-RMQ问题(ST算法)

    RMQ(Range Minimum/Maximum Query)问题,是求区间最大值或最小值,即范围最值问题。暴力解法是对每个询问区间循环求解,设区间长度 ...

    唔仄lo咚锵
  • 【算法】动态规划(三)

    考虑仅用1分、5分、10分、25分和50分这5种硬币支付某一个给定的金额。 例如需要支付11分钱, 有一个1分和一个10分、 一个1分和两个5分、 六个...

    MapleYe
  • 【算法】动态规划(二)

    上一篇,介绍了动态规划DP的概念,以及暴力递归和动态规划的关系。这一篇,将介绍几道经典的动态规划题

    MapleYe
  • 【算法】动态规划(一)

    1、动态规划(英语:Dynamic programming,简称DP)通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 2、动态规划常常适用于有重...

    MapleYe
  • 动态规划算法(01背包问题)

    动态规划算法和分治算法类似,也是将待求解问题分成若干个小问题一步步求解,不同的是,每一个小问题求解过程依赖于上一个小问题的解。动态规划问题可以通过填表法来得到解...

    贪挽懒月
  • 动态规划算法秘籍

    动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和...

    rainchxy
  • 动态规划算法学习

    http://blog.csdn.net/nevasun/article/details/6977511

    bear_fish
  • 初级算法-动态规划

    动态规划主要是解一些递归问题,也就是将递归写成非递归方式,因为编辑器无法正确对待递归,递归方法会导致很多计算结果被重复计算,比如菲波那切数列。

    方丈的寺院
  • 【算法学习】动态规划

    动态规划(dynamic programming)是一种基础的算法设计思想。作为一种寻找最优解的通用方法,它是在20世纪50年代由美国数学家Richard Be...

    短短的路走走停停
  • 算法基础:动态规划

    动态规划与分治法的区别是:从分治法的视角来看,每个子问题必须相互独立;但在多轮决策中,这个假设显然不成立,而多轮决策就用到了动态规划方法。

    RendaZhang
  • 算法篇:动态规划(一)

    本篇是动态规划的第一篇文章,对于动态规划的题目,其实就是数学中的归纳法,最终需要找到一个公式,找到后面的值与前面数据之间的关联关系。

    灰子学技术
  • 算法篇:动态规划(二)

    本篇属于动态规划的进阶题目,我们可以通过数据dp[i]来表示包括第i个元素的计算和,然后计算出所有的dp[i],最终求出来最大值就可以。详细见下面的例子中的讲...

    灰子学技术
  • 算法刷题:LC初级算法(六)动态规划类

    给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

    看、未来
  • 动态规划算法 ——钢条切割问题

    长度为n米的钢条,需要切割成x断来贩卖。假设没有切割成本,且每种长度能够销售的价格是一个确定的值(例如长度1米可以卖1元,长度2米可以卖5元,长度3米可以卖6元...

    用户1327360

扫码关注云+社区

领取腾讯云代金券