动态规划算法

三角形最小路径和
解题思路见:
https://leetcode.cn/problems/triangle/solutions/329143/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
可以看下官方解题思路

方法一:动态规划

  • 思路与算法


    思路与算法.png
  • 细节


    细节.png
  • Javascript实现

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let n = triangle.length
    let f=[...triangle]
    f[0][0]=parseInt(triangle[0][0])
    for(let i=1;i<n;i++){
      f[i][0]=f[i-1][0]+parseInt(triangle[i][0])
      for(let j=1;j<i;j++){
        f[i][j]=Math.min(f[i-1][j-1],f[i-1][j])+parseInt(triangle[i][j])
      }
      f[i][i]=f[i-1][i-1]+triangle[i][i]
    }
    let minTotal=f[n-1][0]
    for(let i=1;i<n;i++){
      minTotal=Math.min(minTotal,f[n-1][i])
    }
    return minTotal
};

复杂度分析:

  • 时间复杂度:O(n^2) 其中 nnn 是三角形的行数。
  • 空间复杂度:O(n^2) 我们需要一个 n∗n的二维数组存放所有的状态。

方法二:动态规划 + 空间优化

  • 思路与算法👇


    动态规划 + 空间优化 思路与算法.png
  • Javascript实现

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let n = triangle.length
    let f=[...triangle.slice(0,2)]
    console.log(f)
    f[0][0]=parseInt(triangle[0][0])
    for(let i=1;i<n;i++){
      let curr = i % 2
      let prev = 1 - curr
      f[curr][0]=f[prev][0]+parseInt(triangle[i][0])
      for(let j=1;j<i;j++){
        f[curr][j]=Math.min(f[prev][j-1],f[prev][j])+parseInt(triangle[i][j])
      }
      f[curr][i]=f[prev][i-1]+triangle[i][i]
       console.log(f)
    }
    console.log(f)
    let minTotal=f[(n-1)%2][0]
    for(let i=1;i<n;i++){
      minTotal=Math.min(minTotal,f[(n-1)%2][i])
    }
    return minTotal
};
  • 继续优化!


    如何继续优化?使用的空间从2n变成n.png
  • Javascript实现

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let n = triangle.length
    let f=[...triangle.slice(-1)]
    console.log('f初始值',f)
    f[0]=parseInt(triangle[0][0])
    for(let i=1;i<n;i++){
      f[i]=f[i-1]+parseInt(triangle[i][i])
      for(let j=i-1;j>0;j--){
        f[j]=Math.min(f[j-1],f[j])+parseInt(triangle[i][j])
      }
      f[0]=f[0]+triangle[i][0]
       console.log(f)
    }
    console.log('f最终值',f)
    let minTotal=f[0]
    for(let i=1;i<n;i++){
      minTotal=Math.min(minTotal,f[i])
    }
    return minTotal
};
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  let row = triangle.length
  let dp=new Array(row)
  // console.log(dp)
  dp[0]=triangle[0][0]
  for(let r=1;r<row;r++){
    dp[r]=dp[r-1]+triangle[r][r]
    for(let c=r-1;c>0;c--){
      dp[c]=Math.min(dp[c],dp[c-1])+triangle[r][c]
    }
    dp[0]=dp[0]+triangle[r][0]
    // console.log(dp)
  }
  let min = dp[0]
  for(let i=1;i<dp.length;i++){
    min=Math.min(min,dp[i])
  }
  // console.log(min)
  return min
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 217,657评论 6 505
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,889评论 3 394
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,057评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,509评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,562评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,443评论 1 302
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,251评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,129评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,561评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,779评论 3 335
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,902评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,621评论 5 345
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,220评论 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,838评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,971评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,025评论 2 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,843评论 2 354

推荐阅读更多精彩内容