专栏首页女程序员的日常_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 条评论
登录 后参与评论

相关文章

  • 前端路由两种模式:hash与history

    SPA需要在不刷新页面的情况下做页面更新,这就需要前端路由。实际上,前端路由是利用浏览器的hash和history属性

    用户3258338
  • this怎么那么难呢?(接上篇-1)

    2019年12月22日,星期六。距离新年还有9天了,宝宝们可以提前想想2020年的目标了。也可以把目标留言在文章下方,目标说给别人听能起到督促自己的作用,不信你...

    用户3258338
  • Nginx——location常见配置指令,alias、root、proxy_pass

    1、【alias】——别名配置,用于访问文件系统,在匹配到location配置的URL路径后,指向【alias】配置的路径。如:

    用户3258338
  • 程序员面试金典 - 面试题 17.13. 恢复空格(DP+Trie树)

    哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。 像句子"I reset the computer. It still didn’...

    Michael阿明
  • LintCode 编辑距离题目分析代码

    给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

    desperate633
  • 一天一大 leet(整数拆分)难度:中等-Day20200730

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

    前端小书童
  • 动态规划:整数拆分,你要怎么拆?

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

    代码随想录
  • 动态规划:爬楼梯

    所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划了。

    代码随想录
  • LeetCode 70. Climbing Stairs

    ShenduCC
  • 动态规划:斐波那契数

    题目地址:https://leetcode-cn.com/problems/fibonacci-number/

    代码随想录

扫码关注云+社区

领取腾讯云代金券