多多的电子字典

添加个golang的解析，思路与其他人差不多

package main

import "fmt"

func main() {
    n, m, k := 0, 0, 0
    fmt.Scanf("%d %d %d", &n, &m, &k)
    dp := make([][]uint64, n+1)
    //构造动态规划二维数组dp[n][m]
    //dp[i][j]代表i个a，j个b所能拼接出的所有可能字符串的数量
    for i := 0; i <= n; i++ {
        dp[i] = make([]uint64, m+1)
        dp[i][0] = uint64(i)
    }
    for j := 0; j <= m; j++ {
        dp[0][j] = uint64(j)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            dp[i][j] = 1 + dp[i-1][j] + 1 + dp[i][j-1]
        }
    }
    res := ""
    tmp := uint64(k)
    ac, bc := n, m
    for tmp != 0 {
        //如果b的数量没了，则剩下的要填补a
        if bc == 0 {
            var i uint64
            for i  = 0; i < tmp; i++ {
                res += "a"
            }
            break
        }
        //如果a的数量没了，则剩下的要填补b
        if ac == 0 {
            var i uint64
            for i = 0; i < tmp; i++ {
                res += "b"
            }
            break
        }
        // 如果当前的字符是a 则tmp的上限是 1+dp[ac-1][bc]（dp[ac-1][bc]为ac-1个a,bc个b 所能拼接出的所有可能字符串的数量）；
        // 否则 当前字符应该是b
        if tmp <= 1+dp[ac-1][bc] {
            res += "a"
            tmp -= 1
            ac--
        } else {
            res += "b"
            tmp -= 1 + dp[ac-1][bc] + 1
            bc--
        }
    }
    fmt.Printf("%s",res)
}

由不同的前缀a和b构成了两个子树，找第k个元素实际上就是先序遍历的过程，通过求子树中的唯一字符串个数可以快速地跳过一些无关的子树。

直接先序遍历往往会有过大的时间复杂度，可以通过带备忘录的递归算法求解出f(n,m)的值，从而避免大量的重复运算。

Base case:只有m或n不为零，则直接返回对应的值。

# 计算包含N个a和M个b的子字典树包含的unique字符串的个数，从而和K进行
# 比较，以便选择跳过该子树或者进入该子树
count_dict = {}
def calc_subtree_str_num(N,M):
    if (N,M) in count_dict.keys():
        return count_dict[(N,M)]
    elif N == 0:
        count_dict[(N,M)] = M
    elif M == 0:
        count_dict[(N,M)] = N
    else:
        #分别以a和b得到的两个子树的个数统计加上a和b这两个节点
        count_dict[(N,M)] = calc_subtree_str_num(N-1,M) + calc_subtree_str_num(N,M-1) + 2
    return count_dict[(N,M)]

def main():
    N,M,K = list(map(int,input().split()))

    res = ""
    #当K=0时就找到了对应的字符串
    while K > 0:
        # 一般情况 N 和 M 都存在
        if N > 0 and M > 0:
            #获取当前情况下左子树的字符串个数，如果大于K说明结果在右子树
            left_str_cnt = calc_subtree_str_num(N-1, M)+1
            if K <= left_str_cnt:
                # 说明第k个在a子树下，添加字符'a'，并继续循环向下判断
                res += 'a'
                K -= 1 
                N -= 1
            else:
                # 在右子树下，K可以跳过left_str_cnt+1个值，1为左子树根节点'a'，配合上前缀也是一个unique的str
                res += 'b'
                K -= (left_str_cnt + 1)
                M -= 1
        #其他情况，N=0或者M=0时只需要一直添加字符即可,因为题上的说明不用考虑不存在
        elif N == 0 and M > 0:
            res += 'b'
            K -= 1
            M -= 1
        elif M == 0 and N > 0:
            res += 'a'
            K -= 1
            N -= 1
    return res

print(main())

#include <iostream>
#include <string>
#include <map>
using namespace std;
map<pair<int,int>,unsigned long long> ma;

unsigned long long f(int m,int n)
{
    if(ma.count({m,n}))return ma[{m,n}];
    if(!m)ma[{m,n}]=n;
    else if(!n)ma[{m,n}]=m;
    else ma[{m,n}]=f(m-1,n)+f(m,n-1)+2;
    return ma[{m,n}];
}

int main()
{
    long long k;
    int n,m;
    cin>>n>>m>>k;
    string cur="a";
    n--;
    k--;
    while(k>0&&(m||n))
    {
        unsigned long long step=f(n,m)+1;//子树的个数
        if(step>k)//k在子树中
        {
            k--;
            if(n)
            {
                cur+="a";
                n--;
            }else{
                cur+="b";
                m--;
            }
        }else{//k不在子树中，在下一个子树里
             k-=step;
             n++;
             m--;
             cur.back()++;
        }
    }
    cout<<cur<<endl;
    return 0;
}

 
回溯不可以的话，相当N特别大，所以考虑用字典序在O（N）复杂度下解决该问题。 
字典序又叫trie树，该算法思想在实际生活中大量应用。 
默认大家有trie树的基础知识，下面这种方式就是根据构建的字典序进行适当的剪枝，因为我们并不需要遍历每一颗树。 只需要通过数学公式推导出我们想要的结果在哪个子树即可。
本题相当于有两个树，以a开头和以b开头的两颗二叉树。 每一次的cal_step函数是返回以当前节点"a"或者"b"开头的前序遍历需要经过的步数，这个不是由动态规划得到一个dp二维数组，然后直接返回即可。 
这里说一下动态规划的递推公式： dp[i][j] = dp[i-1][j] + 1 + dp[i][j-1] + 1 什么意思呢？ 我看评论里也有人说了，就是返回以"a"开头的和以"b"开头的个数。 可能有人还是不理解，这个时候拿出笔来写一写就明白了。
比如a[2][1] = dp[1][1] + dp[2][0] + 2 dp[1][1] + 1是以"a"开头的个数，即我们可以固定一个"a"在开头
这样就少了一个a可以用，那么只剩下了[a,b]可以组合 即：a,ab,ba,b; 然后再和固定的a开头的字母"a"组合，即aa,aab,aba,ab，这个时候组合就相当于是dp[1][1] 
以a开头的组合显然少了一个"a"这个特殊的组合，显然dp[1][1] + 1才是以"a"开头的组合个数。
题解如下： 







line = list(map(int,sys.stdin.readline().strip().split()))
n = line[0]
m = line[1]
k = line[2]
class Solution:
    map = dict()
    def findKthNumber(self, n: int, m: int, k: int) -> int:
        # dp[i][j] 表示i个a,j个b所能构成的字母组合
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = i
        for i in range(m + 1):
            dp[0][i] = i
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                # i个a和j个b组成的个数为以a开头的和以b开头的加上特殊的a和b
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 2
        def cal_step(n, m):
                return dp[n][m] + 1
        cur = "a"
        # 第一次，应该是以'a'开头的
        n -= 1
        k -= 1
        while k > 0 and (n or m):
            step = cal_step(n, m)
            if step <= k:  # k在下一个子树中
                k -= step
                # 此时的n,m是为了计算dp[m][n]
                # 一轮过后，需要计算以b开头的，所以m-=1,n+=1
                n += 1
                m -= 1
                cur = cur[:-1] + "b"
            else:  # 在子树中
                k -= 1
                if n:
                    cur += "a"
                    n -= 1
                else:
                    cur += "b"
                    m -= 1
        return cur
print(Solution().findKthNumber(n, m, k)) 

def getcount(map,m,n):
    if not m:
        map[(m,n)]=n
    if not n:
        map[(m,n)]=m
    elif (m,n) in map:
        return map[(m,n)]
    else:
        #＋'a'就是getcount(map,m-1,n)+1，加'b'同理
        map[(m,n)]=getcount(map,m-1,n)+getcount(map,m,n-1)+2
    return map[(m,n)]


def mink(n,m,k):
    cur=""
    map= {}
    while k>0 :
        if n>0 and m==0:#只有'a'存在
            k-=1
            cur+="a"
            n-=1
        elif m>0 and n==0: #只有'b'存在
            cur+='b'
            k-=1
            m-=1
        elif n>0 and m>0 :#都存在时
            #计算a下所有子节点的和
            cnt=getcount(map,n-1,m) +1
            if cnt>=k:#在a子树下
                cur+='a'
                k-=1 #k相当于横向遍历，每次向右遍历一个节点
                n-=1
            else:#在b子树下
                cur+='b'
                m-=1
                k-=(cnt+1) #k要减去a子树的所有节点个数
    return cur


from collections import defaultdict

ss=list(map(int,input().split()))
n=ss[0]
m=ss[1]
k=ss[2]
p=mink(n,m,k) 
print(p)

global rec
rec = {}
def count(N, M):
    global rec
    if not N:
        return M 
    if not M:
        return N 
    if (N, M) in rec:
        return rec[(N, M)]
    rec[(N, M)] = count(N-1, M) + 1 + count(N, M-1) + 1
    return rec[(N, M)]

def helper(N, M, K):
    global rec, ans
    count(N, M)
    ans = ''
    def dfs(N, M, K, res):
        global ans
        if K<=0:
            ans = res
            return
        elif not N:
            ans = res + 'b' * K
            return 
        elif not M:
            ans = res + 'a' * K 
            return 
        #print(N, M, K, count(N-1, M))
        if count(N-1, M)+1 >= K:
            dfs(N-1, M, K-1, res+'a')
        else:
            dfs(N, M-1, K-count(N-1, M)-2, res+'b')
    dfs(N, M, K, '')
    print(ans)