序关系计数问题

深藏阁楼爱情的钟 2022-01-14 15:55 168阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

![160003_8F2X_273632.png][]

![160019_2XUc_273632.png][]

这题以前做过，印象还是挺深刻的。  
如果我们把不同的变量看成是不同的小球，如果两个变量相等的话，那么对应的小球就在同一个箱子里（箱子们有序地排成一行）。那么，原问题就等价于：  
将n个不同的小球放进若干个不同的箱子，且箱子数最多为n，最小为1，每个箱子都不为空，问有多少种方案。  
  
设f(i, n)表示把 i 个小球放进n个有序箱子的方案数，那么转移方程为：  
f(i, n) = f(i - 1, n) \* n + f(i - 1, n - 1) \* n  
这个方程的含义是：  
假设存在一个方案使得i个小球在n个箱子里面，如果我们把小球i（小球的编号从1开始）从箱子里拿出来，那么可能出现的情况是：  
（1）小球i所在的箱子还有其他小球  
（2）小球i所在的箱子变空了  
  
对于情况一，转移为：  
将前n-1个小球放进n个箱子，然后将小球i放进那n个箱子里的其中一个，方案数为 f(i - 1, n) \* n  
对于情况二， 转移为：  
将前i - 1个小球放进n-1个箱子，然后将小球i放进第n个箱子，最后将第n个箱子往已有的那n-1个箱子插进去，方案数为f(i - 1, n - 1) \* n

#include <cstdio>
    #include <vector>
    using namespace std;
    
    vector< vector< int > > f;
    
    template <class VVType, class T>
    void make2DVector(VVType & a, int d, int f, const T & initValue) {
        int i, j;
        a.resize(d);
        for (i = 0; i < d; ++i) {
            a[i].resize(f);
            for (j = 0; j < f; ++j) a[i][j] = initValue;
        }
    }
    
    
    int dp(int i, int n) {
      if (i == 1) {
        return n == 1 ? 1 : 0;
      }
      if (f[i][n] != -1) return f[i][n];
    
      int & ans = f[i][n];
    
      ans = (dp(i - 1, n) + dp(i - 1, n - 1)) * n;
      return ans;
    }
    
    int main() {
      int k;
      scanf("%d", &k);
      make2DVector(f, k + 1, k + 1, -1);
    
      int i, j;
      for (i = 1; i <= k; ++i)
        for (j = 1; j <= i; ++j)
          dp(i, j);
      int sum = 0;
      for (j = 1; j <= k; ++j)
        sum += dp(k, j);
      printf("%d\n", sum);
      return 0;
    }

转载于:https://my.oschina.net/mustang/blog/58109

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/9752d42ae8114defbd46f0d6ce7ae324.png
[160003_8F2X_273632.png]: /images/20220114/1c91fa337c53466193692ee27f0952be.png
[160019_2XUc_273632.png]: /images/20220114/bdffa40cd7ff4793875d6e58809c4ab8.png