• 百度2017春招笔试真题编程题:不等式数列

    05/15 chency 3 评论  , 

度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 ‘>’ 和 ‘<‘ )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即(‘<”)和n-k-1个大于符号(即’>’),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

输入描述:

输入包括一行,包含两个整数n和k(k < n ≤ 1000)

输出描述:

输出满足条件的排列数,答案对2017取模。

输入例子:

5 2

输出例子:

66

1 收藏


直接登录
最新评论
  • 豪满   5 天前

     

  • rowan Scala开发 4 天前

    楼上的做法略显暴力,我的想法如下:

    dp[n][k] 代表对于1-n的排列,有k个小于号的排列个数。

    那么:

    • rowan Scala开发 3 天前

      之前写的有点小问题,纠正一下