动态编程：为什么要以相反的顺序更新数组？

Question

我想通过LeetCode.119这个问题。帕斯卡三角区II

给定一个非负指数k，其中k≤33，返回帕斯卡三角形的第k个指数行。

注意，行指数从0开始。

在帕斯卡三角形中，每个数字都是它上面的两个数字之和。

例子：在帕斯卡三角形中，每个数字都是上面两个数字之和。输入： 3Output: [1,3,3,1]: [1,3,3,1]跟进。

你能优化你的算法，只用O(k)个额外空间吗？

import java.util.Arrays;
class Solution {
    public List<Integer> getRow(int rowIndex) {
    Integer[] dp = new Integer[rowIndex+1];
    Arrays.fill(dp,1);
    for(int i = 2; i <= rowIndex;i++){
        for(int j = i- 1; j > 0;j--){
            dp[j] = dp[j-1] + dp[j];
        }
    }
    return Arrays.asList(dp);
    }
}

我看到有人给出了这个工作方案.我可以理解为什么它是正确的.但我还是很不清楚为什么数组是按这个顺序更新的.在这种情况下，我知道状态的转换是这样的。

P(n) = P(n-1) + P(n)

但是，这怎么能给如何选择更新数组的方向提供线索呢？如果我们用DP的方式思考，升序到底为什么在这种情况下不起作用。我知道实质上这可能造成重复计算。

我知道这可能是微妙的，但还是有人能至少在这一点上投下一点光亮。

Answer 1

可能的公式 P_n = P_n-1 + P_n 带来困惑，因为它不是真正的递归关系。如果是的话，它将是无限的。

真正的递归关系是由以下公式给出的。

P_行，n = P_行-1，n-1 + P_行-1，n

或者用更完整的说法。

• ∀ n∈{1，行-1}。P_行，n = P_行-1，n-1 + P_行-1，n
• P_行，0 = 1
• P_{n, n} = 1

如果你要天真地实现这一点，你将创建一个二维DP矩阵。从第0行开始，你将使用上面的递归关系，从一行到下一行建立DP矩阵。

然后你会发现，你只需要前一行的DP数据来计算当前行的数据。所有在前一行之前的DP行都是空闲的：它们没有任何作用了。它们是在浪费空间。

所以你决定不创建整个DP矩阵，而只创建两行。一旦你完成了这个DP结构的第二行，你就把这一行变成第一行，并重新设置DP结构中的第二行。然后你可以继续填充第二行，直到它再次完成，你重复这种 "移位 "的行数......。

现在我们来到最后一个优化，这就涉及到你的问题。

实际上，你可以只用一条DP行来完成。这条行将代表之前的DP行和当前的DP行。要做到这一点，你需要从右到左更新那行。

每一个被更新的值都被认为是 "当前行"，而你读取的每一个值都被认为是 "前一行"。这样递归关系的右边指的是之前的DP行，左边（就是分配的）指的是当前行。

这只适用于从右到左的情况，因为递归公式从来没有提到过 n+1但要 n 至多是指。如果是指 n 和 n+1那你就得从左往右走。

此刻我们 阅读 临界值 n，它仍然是对应于之前的DP行的值，一旦我们写到它，就不再需要之前的那个值了。而当我们 阅读 临界值 n-1 我们确定它仍然是前一行的值，因为我们从右边来，而且还没有更新它。

你可以想象我们是如何用 "当前 "行的新值来擦拭和替换 "前一条 "行的值的。

希望这能让你明白一点。