[动态规划] 五、三角形的最小路径和

题目

如上所示，以上三角形由一连串的数字构成，要求从顶点 2 开始走到最底下边的最短路径，
每次只能向当前节点下面的两个节点走，如 3 可以向 6 或 5 走，不能直接走到 7。
条件
三角形：一连串数字组成（用二维数组存储）
限制：只能向当前节点的下面两个节点走

动态规划问题建模阶段

设三角形值为 value[ [2], [3,4], [6,5,7], [4,1,8,3] ]

底层      |   4   1   8   3
倒数第2层 |   7   6   10
倒数第3层 |   9  10
顶层      |  11

规律：
底层：一开始都是最小
倒数第二层：min(6+4, 6+1)=7、min(5+1, 5+8)=6、min(7+8,7+3)=10
倒数第三层：min(3+7, 3+6)=9、min(4+6, 4+10)=10
顶层：min(2+9, 2+10)=11

由此可见，只需要存储前面的最小路径数，就可推出后面的最小路径数

动态规划三个重要的概念

最优子结构：
由于有两种走法，所以2往下走有两种方案（选最小值）
2往下走 = min( 2+3, 2+4 )
边界：
最底层 4,1,8,3 是最小的
转态转移公式：
d[i,j] = min(d[i+1,j], d[i+1,j+1]) + value[i,j]
(例：d[2,0] = min(d[3,0],d[3,1]) + value[2,0]，即 d[2,0]=min(4,1)+6=7)

动态规划求解问题阶段

<?php

namespace app\index\controller;

// 动态规划求解问题阶段：
class Index
{
    /**
     * 动态规划（Dynamic Programming）
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public function test()
    {
        $value = [
            [2],
            [3,4],
            [6,5,7],
            [4,1,8,3]
        ];

        $value_len = count($value);         // 三角形的层数
        $min       = $value[$value_len-1];  // 初始值为数组底层值

        // 循环三角形数组，自底向上，从倒数第二层开始
        for ($i = $value_len - 2; $i >= 0; $i--) {

            $sub_len = count($value[$i]);   // 每层的长度

            // 循环每层的数字，从左到右
            for ($j = 0; $j < $sub_len; $j++) {
                $min[$j] = min($min[$j], $min[$j + 1]) + $value[$i][$j];
            }
        }
        echo $min[0];
    }
}