假设我有两个大小为m和n的数组:
a[1] a[2] a[3] ..... a[m]
和
b[1] b[2] b[3] ..... b[n]
我想要形成一个新的数组,合并这两个数组,使得在新的由m + n个元素组成的数组中,a[i]总是放在a[i + 1]之前,b[i]总是放在b[i + 1]之前。例如,a[1] a[2] b[1] b[2]... b[n] a[m]将是一个有效的数组,但a[2] a[1] b[1] b[2] ... b[n] a[m]不是。给定m和n,重复允许时有多少种这样的组合?
我有解决问题的直觉:
- b[1] - b[2] - b[3] - ..... - b[n]
我可以将a[1]放置在b数组内n-1个位置中的任何一个位置上,并考虑到第一个和最后一个位置,我共有n+1个放置a[1]的方式。如果我将a[1]放在第一个位置(就在b[1]之前),我现在可以将a[2]放在n+1个位置。但是如果我将a[1]放在b[1]之后,我将有n种放置a[2]的方法。我可以递归地应用这种方法来处理所有a[i],其中1≤i≤n。但是我找不到任何数学公式来表示解决方案,此外,我不知道如何处理允许重复的情况。
a[1] a[2] a[3] ..... a[m]
和
b[1] b[2] b[3] ..... b[n]
我想要形成一个新的数组,合并这两个数组,使得在新的由m + n个元素组成的数组中,a[i]总是放在a[i + 1]之前,b[i]总是放在b[i + 1]之前。例如,a[1] a[2] b[1] b[2]... b[n] a[m]将是一个有效的数组,但a[2] a[1] b[1] b[2] ... b[n] a[m]不是。给定m和n,重复允许时有多少种这样的组合?
我有解决问题的直觉:
- b[1] - b[2] - b[3] - ..... - b[n]
我可以将a[1]放置在b数组内n-1个位置中的任何一个位置上,并考虑到第一个和最后一个位置,我共有n+1个放置a[1]的方式。如果我将a[1]放在第一个位置(就在b[1]之前),我现在可以将a[2]放在n+1个位置。但是如果我将a[1]放在b[1]之后,我将有n种放置a[2]的方法。我可以递归地应用这种方法来处理所有a[i],其中1≤i≤n。但是我找不到任何数学公式来表示解决方案,此外,我不知道如何处理允许重复的情况。