MathLabs

第5题

设 nn 为正整数。一个日本三角形由排成等边三角形状的 1+2+⋯+n1+2+\cdots+n 个圆圈组成，使得对每个 i=1,2,…,ni=1,2,\ldots,n，第 ii 行恰好有 ii 个圆圈，其中恰好一个被染成红色。日本三角形中的忍者路径是指从最顶行出发，每次从一个圆圈走到其正下方两个圆圈之一，最终止于最底行的 nn 个圆圈组成的序列。用 nn 表示，求最大的 kk，使得每个日本三角形中都存在一条至少包含 kk 个红色圆圈的忍者路径。
第 3/5 步：递归地计算最优部分路径
上一步下一步
通俗地说

以某个给定圆圈结尾的部分忍者路径所能达到的最大红色圆圈数，只取决于以其两个可能的前驱圆圈结尾的两条最优部分路径。

f(i,j)=max⁡{f(i−1,j−1),f(i,j−1)}+[circle (i,j) is red]f(i,j)=\max\{f(i-1,j-1),f(i,j-1)\}+[\text{circle }(i,j)\text{ is red}]
详细分析

对任意日本三角形，令 f(i,j)f(i,j) 表示从最顶端的圆到第 jj 行第 ii 个位置的圆的忍者路径段上红色圆圈的最大数目（若该位置不存在则 f(i,j)=0f(i,j)=0）。由于经过 (i,j)(i,j) 的每条路径都来自 (i−1,j−1)(i-1,j-1) 或 (i,j−1)(i,j-1)，若 (i,j)(i,j) 是红色圆圈，则 f(i,j)=max⁡{f(i−1,j−1),f(i,j−1)}+1f(i,j)=\max\{f(i-1,j-1),f(i,j-1)\}+1；否则 f(i,j)=max⁡{f(i−1,j−1),f(i,j−1)}f(i,j)=\max\{f(i-1,j-1),f(i,j-1)\}。