动态规划找出对于每个索引j，所有递增的子序列的数目都以给定序列中的Xj结束

Question

给定一个实数序列(X1，X2，...，Xn)。写一个高效的算法，找到每个索引j的严格递增的子序列的数量，以Xj结束。

定义了一个严格递增的子序列: Xa1，Xa2，..，Xai when a1 < a2 .< ai，维护: Xa1 < Xa2 < ..< Xai.如果ai = j)，则子序列以Xj结束

我的解决方案应该包括一个在O(n^2)中解决这个问题的递归公式和一个正确性证明，我只能使用嵌套的for循环来解决它，我不确定是否有O(n^2)递归解决方案。

List a[1…n] <- [1…1]
 For j= 1 to n
    For i= 1 to j-1
       If xi<xj then
          a[i]= a[j]+a[i]; 

Answer 1

当你执行a[i] = a[j] + a[i]时，你实际上就是在执行a[i]++，因为你每次运行这行代码时都会执行a[j]==1。如果这一点不是一目了然，您应该手动跟踪代码的执行，并查看它实际在做什么。

你可能想要的是：

for j in range(n):
    for i in range(j):
        if x[i] < x[j]:
            a[j] += a[i]

递归关系是:以j结尾的递增子序列的数量等于以小于j的每个索引结尾的递增子序列的数量之和，对于只包含j的序列，加1。

分析

这是一个O(n^2)解。证明:在外部循环的第一次迭代中，我们在内部循环中循环1次(内部循环在每次迭代中进行恒定的计算量)。每增加一次j，我们就会增加内部循环中的迭代次数。所以我们最终在内部循环中调用代码，总共调用了1 + 2 + 3 + ... (n-1) + n次。让f(n) = 1 + 2 + 3 + ... n来吧。

回想一下big-O的definition：f(n) = O(n^2)意味着存在正常量c和k，使得0 ≤ f(n) ≤ cn^2适用于所有n ≥ k。对于函数f，c和k的值必须是固定的，并且不能依赖于n。

显然是0 ≤ f(n)，所以我们只需要证明存在一些c和k，使得f(n) ≤ cn^2适用于所有的n ≥ k。我将选择c=1和k=1。您可以验证所有n的f(n) <= n^2。

虽然你没有问，但你在下面的评论表明你想要证明这是我们能得到的最严格的界限。所以我会证明f(n) = Ω(n^2)

如果对于某个常数c>0和所有足够大的n，f(n) ≥ cn^2。

让我们选择c=4。然后是f(n) = 1 + 2 + 3 + ... n >= (n/2) + (n/2)+1 + (n/2)+2 + ... n，我们从f(n)中减去1 + 2 + ... (n/2)-1，得到这个不等式。

还有，(n/2) + (n/2)+1 + (n/2)+2 + ... n >= (n/2)*(n/2)，因为我们可以获取所有的n/2项，这些项都是>= n/2，并将它们的下限精确地定义为n/2。

但是(n/2)*(n/2) = (n^2)/4，所以我们对所有n都有f(n) >= (1/4)n^2，所以我们已经证明了f(n) = Ω(n^2)。

Answer 2

所以基本上你想要一种自顶向下的方法？这个怎么样？

​

#include<bits/stdc++.h>
using namespace std;

int dp[15] = {0};
int a[15] = {3,2,1,14,2,4,5,9,7,20,12,13,6,8,11};

int DP(int x){
	if(x == 0) return 1;
	if(dp[x]) return dp[x];
	int ret = 1;
	for(int i=0; i<x; i++) if(a[x] > a[i]) ret += DP(i);
	return dp[x] = ret;
}
int main(){
	printf("%d\n", DP(14));
	return 0;	
}

​

递归公式是相同的，它不依赖于您如何实现解决方案(自上而下或自下而上)

这就是它：

​

​