網易筆試：小易喜歡的數列

網易筆試：小易喜歡的數列（終于不逾時了）

題目描述

小易非常喜歡擁有以下性質的數列:

1、數列的長度為n

2、數列中的每個數都在1到k之間(包括1和k)

3、對于位置相鄰的兩個數A和B(A在B前),都滿足(A <= B)或(A mod B != 0)(滿足其一即可)

例如,當n = 4, k = 7

那麼{1,7,7,2},它的長度是4,所有數字也在1到7範圍内,并且滿足第三條性質,是以小易是喜歡這個數列的

但是小易不喜歡{4,4,4,2}這個數列。小易給出n和k,希望你能幫他求出有多少個是他會喜歡的數列。

輸入描述:

輸入包括兩個整數n和k(1 ≤ n ≤ 10, 1 ≤ k ≤ 10^5)

輸出描述:

輸出一個整數,即滿足要求的數列個數,因為答案可能很大,輸出對1,000,000,007取模的結果。

輸入例子1:

2 2

輸出例子1:

3

思路：

動态規劃的思想，如果能填寫出下面的表格，那麼這道題的思路就了解了：

(1)、n = 3， k = 3時

1	2	3
1	1	1	1
2	1	3	7
3	1	3	7

最後總個數 = 1 + 7 + 7

(2)、n = 3， k = 4時

1	2	3
1	1	1	1
2	1	3	8
3	1	4	12
4	1	4	12

最後總個數 = 1 + 8 + 12 + 12 = 33

java 通過40%用例，結果逾時，(T_T)~

雖然結果逾時，但是對于了解上面的表格還是有點幫助的。

import java.util.*;

public class Main

    public static int M = 1000000007;

    public static int solution(int n, int k) {
        int[][] dp = new int[k][n];
        for(int i = 0; i < k; i++) {
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

        // 一列一列填表
        for(int j = 1; j < n; j++) {
            for(int i = 1; i < k; i++) {
                for(int p = 1; p <= i+1; p++) {
                    dp[i][j] += dp[p-1][j-1];
                    dp[i][j] %= M;
                }
                for(int p = i + 2; p <= k; p++) {
                    if(p % (i+1) != 0) {
                        dp[i][j] += dp[p-1][j-1];
                        dp[i][j] = dp[i][j] % M;
                    }
                }
            }
        }

        int result = 0;
        for(int i = 0; i < k; i++) {
            result += dp[i][n-1];
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int      

import java.util.Scanner;

public class Main

    public static int M = 1000000007;

    public static int solution(int n, int k) {
        int[][] dp = new int[k][n];
        for(int i = 0; i < k; i++) {
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

        for(int j = 1; j < n; j++) {
            // 先求前一列的和
            int sum = 0;
            for(int i = 0; i < k; i++) {
                sum = (sum + dp[i][j-1]) % M;
            }

            // 對于(i+1)的倍數，都不用計算，需要從sum中減掉
            for(int i = 0; i < k; i++) {
                int sum_invalid = 0;
                int p = 2;
                while(p * (i+1) <= k) {
                    sum_invalid = (sum_invalid + dp[p*(i+1)-1][j-1] ) % M;
                    p++;
                }
                dp[i][j] = (sum - sum_invalid + M) % M;
            }
        }

        // 最後一列求和
        int result = 0;
        for(int i = 0; i < k; i++) {
            result += dp[i][n-1];
            result %= M;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int