美文网首页
数字三角形

数字三角形

作者: laochonger | 来源:发表于2018-03-20 14:10 被阅读0次
数字三角形

问题描述和状态定义 —— 非负数字组成的三角形,从第一个数开始每次可以向右或者向下走一格,直到最下行,求沿途经过数和的最大值。这是一个动态决策的问题,每次都面临两种选择,如果用回溯法找所有路线,则n层三角形有2的n次方条的路线,效率很低。

所以引入状态转移的概念:

把当前位置 ( i, j)看成一个状态,定义函数 d( i, j)为从( i, j)出发后能得到的最大的和,那么可以写出一个递推方程:

d( i, j) = a( i, j) + max{ d( i, j + 1), d( i + 1, j + 1)};

d( i, j + 1)为从( i, j + 1)出发的最大和,即一个最优子结构,也可以描述成“全局最优解包含局部最优解”。上式是一个状态转移方程,状态和状态转移方程是动态规划的核心

记忆化搜索与递推
方法一:递归计算

int solve(int i , int j){
     return a[i][j] + ( i == n ? 0 : max( solve(i+1,j), solve(i+1, j+1) )   );
}  //注意处理边界

这样做正确,但重复计算


数字三角形

方法二: 递推计算

int i, j;
for( j = 1; j <= n; j++) d[n][j] + a[n][j];
for(int i = n-1; i >= 1; i--){
    for(int j = 1; j <= i; j++){
        d[i][j] = a[i][j] + max(d[i+1][j] , d[i+1][j+1]);
    }
}

一层一层从下至上递推,复杂度为O(N^2)

方法三:记忆化搜索

int solve(int i, int j){
    if(d[i][j] >= 0) return d[i][j];
    return d[i][j] = a[i][j] + (i == n?0:max(solve(i+1,j), solve(i+1, j+1)));
}//别忘了队d[i][j]赋值

已经搜过则判断后不再计算,直接用该值,由于i,j都在,1~n之间,所有不相同的结点一共只有O(n2)个,不论以怎样的顺序访问,时间复杂度均为O(n2)

数字三角形

相关文章

  • Leetcode 120.Triangle

    这道题的大概意思是,给一个数字构成的三角形,要求找出一条路径使得路径数字之和最小。 比如下面这个三角形的数字和最小...

  • DP(dynamic programming)

    以数字三角形为例:给出一个数字三角形,从顶部到底部有很多路径,求路径最大和。如: 73 88 1 02...

  • 动态规划 2020-03-17

    动态规划 动态规划重要的是:判断状态,状态转移方程 数字三角形 问题描述给定一个数字三角形,找到从顶部到底部的最小...

  • 109. 数字三角形

    109. 数字三角形 描述 笔记 数据 评测 给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下...

  • 动态规划数字三角形

    给定一个由n行数字组成的数字三角形,设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。输...

  • 烧脑题1

    移动3个圆圈, 把左边的三角形变成右边的三角形, 该怎么做呢? 答案: 假设10个三角形是1到10的数字,那么就该...

  • 线性dp

    数字三角形 原题链接[https://www.acwing.com/problem/content/900/] 一...

  • 动规入门 - 数字三角形(从朴素递归到递推的四步优化)

    问题:给定一个由n行数字组成的数字三角形,如下图所示: 试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径...

  • 数字笔记,2

    数字三角形内有2的人,不仅善于沟通,而且能够说到对方的心里去。 三角形里面没有2,外面有2 。婚前2在外面,能说;...

  • 打印机清零

    打开前盖/清除/启用/按三角形标记数字上升到11/OK/关闭前盖

网友评论

      本文标题:数字三角形

      本文链接:https://www.haomeiwen.com/subject/sgtbqftx.html