第三题动态规划算法java实现：如下 时间复杂度应为O(n) 空间复杂度为O(3n) public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); in.nextLine(); for (int i = 0; i < n; i++) { String str = in.nextLine(); System.out.println(getDesignateCount(str.toCharArray())); } in.close(); } public static int getDesignateCount(char[] str) { int dp[][] = new int[3][str.length]; if (str[0] == 'd') dp[0][0] = 1; for (int i = 1; i < str.length; i++) { if (str[i] == 'd') { dp[0][i] = dp[0][i - 1] + 1; continue; } else if (str[i] == 'j' && dp[0][i - 1] > 0) { dp[1][i] = dp[0][i - 1]; dp[0][i] = dp[0][i - 1]; continue; } else if (str[i] == 'i') { int c = 0; for (int k = 0; k < i; k++) c += dp[1][k]; dp[2][i] = c; dp[0][i] = dp[0][i - 1]; continue; } else dp[0][i] = dp[0][i - 1]; } int sum = 0, i = 0; for (; i < str.length; i++) sum += dp[2][i]; return sum; }