当前位置:  首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意:

  1. 给定一个字符串,长度为n,D代表前一个数比下一个数大而I代表前一个数比下一个数小
  2. 求出在所有0-n的排列中,满足上面字符串所代表的排列两两之间大小比较的排列的个数

思路:

  • 最大的那个数,可能出现在下面三种情况:
    • 出现在位置0,a[0]>a[1]
    • 出现在位置i,a[i]>a[i+1]且a[i]<a[i-1]
    • 出现在位置n,a[n]>a[n-1]
  • 枚举最大的数出现的位置,假设为i,当i选定为最大的数后,剩下的数要分配给左右两边,有c(n, i)种情况,并且左右两边的队列互相独立
  • 这时候左右两边分别成了一个命题相同的子问题,求出即可
  • 注意:需要注意的是,不是所有的动态规划都需要用递推的方式求解。这道题可以选择另一种写法,就是递归+缓存,代码量会少不少

代码:

  1. class Solution {
  2. private static int[][] c;
  3. private static int MOD = 1000000007;
  4. private static int[][] cache = new int[202][202];
  5. private void init() {
  6. c = new int[202][202];
  7. c[0][0] = 1;
  8. for (int i = 1;i <= 201;i++) {
  9. c[i][0] = 1;
  10. for (int j = 1;j < i;j++) {
  11. c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
  12. if (c[i][j] >= MOD) {
  13. c[i][j] -= MOD;
  14. }
  15. }
  16. c[i][i] = 1;
  17. }
  18. }
  19. public int find(String S, int left, int right) {
  20. int ret = 0;
  21. if (right - left == 0) {
  22. return 1;
  23. }
  24. if (cache[left][right] != -1) {
  25. return cache[left][right];
  26. }
  27. if (S.charAt(left) == 'D') {
  28. ret += find(S, left + 1, right);
  29. if (ret >= MOD) {
  30. ret -= MOD;
  31. }
  32. }
  33. if (S.charAt(right - 1) == 'I') {
  34. ret += find(S, left, right - 1);
  35. if (ret >= MOD) {
  36. ret -= MOD;
  37. }
  38. }
  39. for (int i = left + 1;i < right;i++) {
  40. if (S.charAt(i) == 'D' && S.charAt(i - 1) == 'I') {
  41. ret += ((long) find(S, left, i - 1) * find(S, i + 1, right) % MOD) * c[right - left][i - left] % MOD;
  42. if (ret >= MOD) {
  43. ret -= MOD;
  44. }
  45. }
  46. }
  47. if (ret == 0) {
  48. return cache[left][right] = 1;
  49. }
  50. return cache[left][right] = ret;
  51. }
  52. public int numPermsDISequence(String S) {
  53. init();
  54. for (int i = 0;i < 202;i++) {
  55. for (int j = 0;j < 202;j++) {
  56. cache[i][j] = -1;
  57. }
  58. }
  59. int ret = find(S, 0, S.length());
  60. return ret;
  61. }
  62. }

该分类下的相关小册推荐: