PHP解决数字三角问题

ゝ一世哀愁。 2022-06-15 05:38 167阅读 0赞

下图给出了一个数字三角形，请编写一个程序，计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。
（1）每一步可沿左斜线向下或右斜线向下
（2）1 < 三角形行数 < 100
（3）三角形数字为0，1，…99

这里写图片描述

通常的算法还是以深度优先，计算过程做状态保留。不过本人觉得如何构造数据结构要比算法本身有趣且难想到的多。

PHP：

  1. public function run($args)
  2. {
  3.     @set_time_limit(0);
  4.     @ini_set('memory_limit', '2048M');
  6.     $obj_arr = array(
  7.         array(7),
  8.         array(3,8),
  9.         array(8,1,0),
  10.         array(2,7,4,4),
  11.         array(4,5,2,6,5),
  12.     );
  13.     $result = array();
  14.     $num = count($obj_arr);
  15.     //逆向循环
  16.     for($i=$num-1;$i>=0;$i--){
  17.         //三角特性使得 $i== count($obj_arr[$i])
  18.         for($j=0;$j<=count($obj_arr[$i]);$j++){
  19.             $result[$i][$j] = max($result[$i+1][$j], $result[$i+1][$j+1])+$obj_arr[$i][$j];
  20.         }
  21.     }
  22.     echo $result[0][0];
  23. }

输出结果：30

发表评论

表情：
评论列表 （有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

    相关 PHP输出杨辉三角

    1、什么是杨辉三角？ 杨辉三角是二项式系数的一种写法，由于排列形状类似于三角形，被称为杨辉三角。 杨辉三角以正整数构成，数字左右对称，每行由1开始逐渐变大，然后变小，回到

    谁践踏了优雅谁践踏了优雅/ 0 赞/ 152 阅读

    相关 PHP解决数字三角问题

    下图给出了一个数字三角形，请编写一个程序，计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 （1）每一步可沿左斜线向下或右斜线向下 （2）1 < 三角

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 168 阅读