java - 需要帮助以了解以下代码为何不起作用

Question

我试图解决leetcode上的最长递增子序列问题，在这里我必须找到数组中最长递增子序列我试图用动态编程（O（n ^ 2）复杂度）来解决它。
我写了两个函数，它们都试图分别解决这个问题，但是只有一个函数起作用。
我试图使用第一个函数的完全相同的逻辑来优化第二个函数，但是我很难找出它为什么不工作。
以下功能工作：

// WORKS
private int dp(int[] a) {
    int[][] dp = new int[a.length+1][a.length+1];
    for(int p = a.length-1; p >=0; p--) {
        for(int i = a.length-1; i >=0; i--) {
            if(i >= a.length)
                dp[p][i] = 0;
            else if(a[i] > a[p])
                dp[p][i] = Math.max(dp[p][i+1], 1 + dp[i][i+1]);
            else
                dp[p][i] = dp[p][i+1];
        }
    }
    return dp[0][0];
}

在第二个函数中，我试图通过使用两列而不是一个完整的矩阵来减少所需的空间，因为我们只需要列i+1的值来填充列i。

// DOES NOT WORK
private int dp_optimized(int[] a) {
    int[] col1 = new int[a.length+1];
    int[] col2 = new int[a.length+1];
    for(int p = a.length-1; p >=0; p--) {
        for(int i = a.length-1; i >=0; i--) {
            if(i >= a.length)
                col1[p] = 0;
            else if(a[i] > a[p]) 
                col1[p] = Math.max(col2[p], 1+col2[i]);
            else
                col1[p] = col2[p];
        }
        for(int i=0; i< col1.length; i++)
            col2[i] = col1[i];
    }
    return col1[0];
}

这基本上不是一回事吗为什么功能1工作而功能2不工作？
调用这些函数的主要方法如下：

public int lengthOfLIS(int[] nums) {

    int[] a = new int[nums.length+1];
    int[][] dp = new int[a.length+1][a.length+1];
    for(int i = 1; i<nums.length+1; i++)
        a[i] = nums[i-1];
    a[0] = Integer.MIN_VALUE;
    // return dp(a)
    return dp_optimized(a);
}

样本输入：nums=[10,9,2,5,3,7101,18]
样本输出：4
任何帮助都将不胜感激谢谢。

Answer 1

让我们从确保正确理解重复开始。
定义：dp[p][i]存储以下问题的答案：
从具有索引[i，a.length（）-1]的元素中选择的整数的最长递增子序列是什么，附加的约束是第一个元素必须大于a[p]（我们将通过将其索引存储在变量p中来跟踪最后一个元素）
重复：dp[p][i]的答案是：
dp[p][i+1]：我们忽略了第i项，得到了同一问题的解，但只考虑了带指数的元素[i+1，a.length-1]
1+dp[i][i+1]：我们决定将第i项作为最优子序列中的整数之一，所以我们计算了所取的元素，现在我们对具有索引[i+1，a.length-1]的元素感兴趣。
只有当第i个元素大于第p个元素时，才能考虑此选择。子问题中的p改为i，这是为了强制下一个要选择的元素必须大于我们刚刚获取的项（第i个元素）
现在我们来讨论代码
N^2内存代码：
我对你的正确代码做了一些修改，让我们看看。

private int dp(int[] a) {
    int[][] dp = new int[a.length+1][a.length+1];
    for(int p = a.length-1; p >=0; p--) {
        for(int i = a.length-1; i >p; i--) {
            dp[p][i] = dp[p][i+1]; // Try to leave the i-th item
            if(a[i] > a[p])        // Try to pick the i-th item
                dp[p][i] = Math.max(dp[p][i], 1 + dp[i][i+1]);
        }
    }
    return dp[0][1];
}

第一次修改：我删除了下面的部分if(i >= a.length) col1[p] = 0;，条件将永远无法满足。
第二个修改：内环在[p+1，a.length-1]之间迭代，因为i必须始终大于p
第三个修改：不是返回dp[0][0]，而是返回dp[0][1]，其中第一个项是未包含在原始数组中的附加元素，其值小于任何其他项（dp[0][1]找到元素[1，a.length-1]的LIS，前提是对要选择的第一个元素没有限制）
内存减少：
让我们进一步考虑一下上面代码的dp表。表中的第一个维度是前一个索引，第二个维度是数组a中的起始索引（我们试图从给定的前一个p开始查找lis）
要减少dp解决方案的内存，您必须问自己两个问题：
1-哪个维度可以缩小？
要回答这个问题，你必须分别检查每个维度，问自己维度的当前值是否是x，我还依赖于当前维度的哪些其他值？这些值中最远的值让我们知道在这个维度上可以减少多少。
让我们把上面的技巧应用到我们的问题上。
维数p：如果p的值是x，那么在第一个子问题dp[p][i+1]中我们不改变x（这是很好的），但是在第二个子问题dp[i][i+1]x被改变为i，并且在rage[i+1，a.length-1]中我取任何值，因此，这个维数是不可约的！
维i：如果i的值是x，那么在第一个子问题中，我们依赖于存储在x+1中的值，在第二个子问题中，我们也依赖于存储在x+1中的值，这很好，很明显，当i的值是x时，我们只需要存储在x+1中的值，我们根本不关心存储在x+2或x+3中的值。。。
我们循环的顺序应该是什么？
当我们进行内存缩减时，循环的顺序很重要，在要缩减的维度上迭代的循环必须是最外层的循环！
当我们的外循环是在第二维i上迭代的循环时，内循环负责计算dp[p][i]的所有值，假设i是常数（换句话说，计算dp表中的一个完整列），在计算之后，我们准备移动到i-1，因为第i列中的所有值都已存储并准备好使用，在计算完第（i-1）列中的所有值之后，我们可以移动到i-2并使用仅存储在第（i-1）列中的答案计算i-2的所有答案，并忽略存储在第i列中的所有值。
所以让我们重新排列代码的循环：

private int dp(int[] a) {
    int[][] dp = new int[a.length+1][a.length+1];
    for(int i = a.length-1; i>0; i--) {
        for(int p = i-1; p>=0; p--) {
            dp[p][i] = dp[p][i+1]; // Try to leave the i-th item
            if(a[i] > a[p])        // Try to pick the i-th item
                dp[p][i] = Math.max(dp[p][i], 1 + dp[i][i+1]);
        }
    }
    return dp[0][1];
}

现在，让我们重新排序并修改您在dp优化函数中编写的代码：

private int dp_optimized(int[] a) {
    int[] col1 = new int[a.length+1];
    int[] col2 = new int[a.length+1];
    for(int i = a.length-1; i>0; i--) {
        for(int p = i-1; p>=0; p--) {
            col1[p] = col2[p];
            if(a[i] > a[p]) 
                col1[p] = Math.max(col1[p], 1+col2[i]);
        }
        for(int p=0; p< col1.length; p++){
            col2[p] = col1[p];
        }
    }
    return col1[0];
}

完成！