上图给出了一个数字三角形.从三角形的顶部到底部有很多条不同的路径.对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和.
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数.此外,向左下走的次数与向右下走的次数相差不能超过 1.
下面的 NNN 行给出数字三角形.与之前做过的[动态规划]数字三角形不同的点是这次要求向左下走的次数与向右下走的次数相差不能超过 1,找规律发现:当三角形行数为偶数时,符合要求的情况下只能走到最底层中间的两格,当行数为奇数时,只能走到最底层中间的一格.所以和上一次一样做状态转移最后根据三角形行数来决定取哪几格整数和的max即可.