Problem A. Password Attacker | Data Structure and Algorithm notes

Problem A. Password Attacker | Data Structure and Algorithm notes
Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:

Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password. However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.

To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on M keys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.

Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735. (And, in fact, there are 32 more possible passwords.)
However, these passwords are not possible:

1357  // There is no fingerprint on key '1'
3355  // There is fingerprint on key '7',
         so '7' must occur at least once.
357   // Eve knows the password must be a 4-digit number.

With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7).

其实简单来讲就是用 M 个 不同的字符组成长度为 N 的字符串，问有多少种不同的排列。这里 M 小于 N，要是大于的话就是纯排列了

这里的动态规划不太明显，我们以状态dp[m][n]表示用 m 个不同的字符能组成长度为 n 的不同字符串的个数。这里需要注意的是最后长度为 n 的字符串中必须包含 m 个不同的字符，不多也不少。接下来就是寻找状态转移方程了，之前可能的状态为dp[m - 1][n -1], dp[m - 1][n], dp[m][n - 1]. 现在问题来了，怎么解释这些状态以寻找状态转移方程？常规方法为正向分析，即分析m ==> n, 但很快我们可以发现dp[m - 1][n]这个状态很难处理。既然正向分析比较麻烦，我们不妨试试反向从n ==> m分析，可以发现字符串个数由 n 变为 n-1，这减少的字符可以分为两种情况，一种是这个减少的字符就在前 n - 1个字符中，另一种则不在，如此一来便做到了不重不漏。相应的状态转移方程为：

dp[i][j] = dp[m][n-1] * m + dp[m - 1][n - 1] * m

第一种和第二种情况下字符串的第 n 位均可由 m 个字符中的一个填充。初始化分两种情况，第一种为索引为0时，其值显然为0；第二种则是 m 为1时，容易知道相应的排列为1。最后返回 dp[M][N].

时间复杂度 $O(mn)$, 空间复杂度 $O(mn)$.

    public static long solve(int M, int N) {
        long[][] dp = new long[1 + M][1 + N];
        long mod = 1000000007;
        for (int j = 1; j <= N; j++) {
            dp[1][j] = 1;
        }
        for (int i = 2; i <= M; i++) {
            for (int j = i; j <= N; j++) {
                dp[i][j] = i * (dp[i][j - 1] + dp[i - 1][j - 1]);
                dp[i][j] %= mod;
            }
        }

        return dp[M][N];
    }

http://blog.csdn.net/dmsehuang/article/details/40807799
使用dynamic programing。dp[i][j]表示使用i个不同的key去排列长度为j的密码的所有排列方法。
状态转移方程是：
dp[i][j] = i * (dp[i-1][j-1] * j + dp[i][j-1])
这样理解：
考虑长度为j的密码，最后一位肯定是i个key里面的一员，因此有i种情况；
最后一位决定之后，考虑前j-1位，有可能前面没有用过这个key，那么有dp[i-1][j-1]种情况；有可能前面已经使用过这个key，那么有dp[i][j-1]种情况。

 public static long solve(int M, int N) {
  long mod = 1000000007;
  long[][] dp = new long[M+1][N+1];
  // base case
  for (int j = 1; j <= N; j++) {
   dp[1][j] = 1;
  }
  // dp
  for (int i = 2; i <= M; i++) {
   for (int j = i; j <= N; j++) {
    dp[i][j] = i * (dp[i-1][j-1] + dp[i][j-1]);
    dp[i][j] %= mod;
   }
  }
  return dp[M][N];
 }

Read full article from Problem A. Password Attacker | Data Structure and Algorithm notes