博客

题目传送门：

点我

NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？

即没有人收到属于自己的邮件。

结合我们的做题步骤：

1）.定义一个能够清楚描述最优子问题的数组（明确数组描述的含义）。

2）.找出数组元素之间的关系式(状态转移方程)

3）.找出初始值

code:

这道题的状态转移方程还是不容易找出的（南首- – ）。

A  B C … N (邮件)

a  b  c … n（邮箱）

假设A放入b

1)如果 B放入a 那么剩下n-1个的邮件或邮箱和abAB都没有了关系记为dp[i] = dp[i-2]

2)如果B没有放入a 那有如下状态：

B C … N (邮件)

a  c … n（邮箱）

dp[i] = dp[i-1]

综合1）2）并且，还有其他情况 A

装入c，装入i的i－1种错误之下，同样都有dp[i－1]＋dp[i－2]种错装法，因此

dp[i] = (i-1) * (dp[i-1] + dp[i-2])

public class LTDP {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int b = sc.nextInt();
            System.out.println(ErrNum(b));
        }
    }

    private static long ErrNum(int num) {
        long [] dp = new long[num + 1];  // dp[i]表示第i个邮件以及之前错装的种类数量
        dp[1] = 0; dp[2] = 1;
        if(num == 2 ){
            return dp[2];
        }
        for(int i = 3 ;i <= num;i++){
            dp[i] = (i - 1) *(dp[i-1] + dp[i-2]);// 转移方程 ：如何得出如上述解释
        }
        return dp[num];
    }
}