奇偶数相等的三角形中的最大路径和
Maximum Path Sum in Triangle with Equal Odd and Even Integers
我得到了一个算法任务，要找到三角形（仅包含正整数）中的最大路径总和，其中路径从顶部元素开始通过相等数量的偶数和奇数整数。路径可以向下或右下。例如：
5
6 7
11 13 5
2 21 14 3
8 9 20 22 23
会return结果是5+6+13+14=38。它不会考虑最后一行，因为这只会导致奇数和偶数的数量不平衡。
我知道用于查找三角形中标准最大路径总和的方法，使用自下而上的动态规划方法。但是，我不知道如何解决这个问题，因为似乎有太多的可能性可以以类似的方式减少它。
我假设每两行应该有一个偶数和奇数整数，但是这并没有考虑这些限制下的所有可能的解决方案，因为路径可能是 [奇数，奇数，奇数，偶数，偶数，甚至]或类似的东西。非常感谢我可以用来解决这个问题的重复或关系的想法。
首先可以从问题陈述中推断出一些要点，
- 如果三角形的大小是奇数，我们忽略最后一行，因为奇数个数=偶数个数路径长度应该是偶数。
- 任意一条路径从上到下的odd/even个数最多为n个
在 standard maximum path sum in a triangle 中，递归由
给出
Dp[i][j] = max(Dp[i + 1][j], Dp[i + 1][j + 1]) + currentElement
所以对于这个问题来解释相等的奇数和偶数，我们需要跟踪每个dp状态中的路径奇偶性（奇数和偶数的数量） .
这意味着重复将变为，
Dp[i][j][k] = max(Dp[i + 1][j][k - parity], Dp[i + 1][j + 1][k - parity]) + currentElement,
其中奇偶校验是当前元素奇偶校验，+1 表示偶数，-1 表示奇数。
答案由 Dp[0][0][number of rows]
给出
这里（link）是在 C++ 中使用自底向上动态规划的解决方案。
我得到了一个算法任务，要找到三角形（仅包含正整数）中的最大路径总和，其中路径从顶部元素开始通过相等数量的偶数和奇数整数。路径可以向下或右下。例如：
5
6 7
11 13 5
2 21 14 3
8 9 20 22 23
会return结果是5+6+13+14=38。它不会考虑最后一行，因为这只会导致奇数和偶数的数量不平衡。
我知道用于查找三角形中标准最大路径总和的方法，使用自下而上的动态规划方法。但是，我不知道如何解决这个问题，因为似乎有太多的可能性可以以类似的方式减少它。
我假设每两行应该有一个偶数和奇数整数，但是这并没有考虑这些限制下的所有可能的解决方案，因为路径可能是 [奇数，奇数，奇数，偶数，偶数，甚至]或类似的东西。非常感谢我可以用来解决这个问题的重复或关系的想法。
首先可以从问题陈述中推断出一些要点，
- 如果三角形的大小是奇数，我们忽略最后一行，因为奇数个数=偶数个数路径长度应该是偶数。
- 任意一条路径从上到下的odd/even个数最多为n个
在 standard maximum path sum in a triangle 中，递归由
Dp[i][j] = max(Dp[i + 1][j], Dp[i + 1][j + 1]) + currentElement
所以对于这个问题来解释相等的奇数和偶数，我们需要跟踪每个dp状态中的路径奇偶性（奇数和偶数的数量） . 这意味着重复将变为，
Dp[i][j][k] = max(Dp[i + 1][j][k - parity], Dp[i + 1][j + 1][k - parity]) + currentElement,
其中奇偶校验是当前元素奇偶校验，+1 表示偶数，-1 表示奇数。
答案由 Dp[0][0][number of rows]
给出
这里（link）是在 C++ 中使用自底向上动态规划的解决方案。