Question

一道编程题（有答案，但是我看不懂）

给你一个数字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.
无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}

麻烦解释一下f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}
的意义吧，谢谢！

Answer 1

这是一道动态规划问题，建议zzy首先阅读动态规划相关内容。
公式的意思是我们通过逐行（从上至下）递推能够得到从最上方的“1”开始到第i+1行第j+1列权值之和的最小值f(i,j)为a[i, j] + min{f(i+1, j)，f(i+1, j + 1)，其中a[i,j]代表数字三角形中第i行第j列的权值。