第一道题

给定一个字符串str，和一个正数k

str子序列的字符种数必须是k种，

返回有多少子序列满足这个条件

已知str中都是小写字母

//递归
    public static int way(String str, int k) {
        int[] array = new int[26];
        for(char ch : str.toCharArray()) {
            int temp = (int) ch;
            temp = temp % 97;
            array[temp] ++;
        }

        return process(array, 0, k);

    }

    public static int process(int[] array, int index, int k) {
        if(index == array.length) {
            return k == 0 ? 1 : 0;
        }
        int p1 = process(array, index + 1, k);
        int p2 = 0;
        if(array[index] != 0 && k > 0) {
            p2 = ((1 << array[index]) - 1) * process(array, index + 1, k - 1);
        }
        return p1 + p2;
    }

    //缓存
    public static int way1(String str, int k) {
        int[] array = new int[26];
        for(char ch : str.toCharArray()) {
            int temp = (int) ch;
            temp = temp % 97;
            array[temp] ++;
        }

        int[][] dp = new int[26 + 1][k + 1];
        for(int i = 0; i