[数据结构与算法]P1521 求逆序对（动态规划dp）C/C++

思路：
当插入第i个数字时，例如插入第4个数字，
当插入在最后一个位置，即xxxi那么此时这串数列的逆序对方案数就是前i-1的方案数，因为在末尾，和任何一个数都不构成逆序对，即f[i-][j] ；
当插入的位置为xxix时，i和后面的一个数字构成了一个逆序对，那么前面i-1个数字必然要有j-1个逆序对才行，即f[i-1][j-1]
接下来便是：f[i-1][j-2],f[i-1][j-3],f[i-1][j-4]…
到ixxx,即循环到第i-1次的时候，方案数是f[i-1][j-i-1]

可以得到：
f[i][j]=sum(f[i-1][j-k]) 0≤k≤i-1

AC代码

#include<iostream>
using namespace std;

int f[110][110*50];

int main()
{
	int n,K;
	cin >> n >> K;
	f[1][0]=1;
	f[2][1]=1;
	f[2][0]=1;
	f[0][0]=1;
	for(int i=3;i<=n;i++)
	{
		for(int j=0;j<=K;j++)
		{
			for(int k=0;k<=j&&k<=i-1;k++)
			{
				f[i][j]=(f[i][j]+f[i-1][j-k])%10000;
			}
		}
	}
	cout << f[n][K] << endl ;
	return 0;
}