算法题/序列：最长回文子序列

题目

给定一个序列，找到它的最长回文子序列。在回文子序列中，元素从前往后读和从后往前读是一样的。 子序列是从另一个序列派生出来的序列，删除一些元素或不删除任何元素，而不改变其余元素的顺序。

示例：

输入："abdbca"
输出：5
解释：最长回文子序列是"abdba"

题解

基础解法

Java

class LPS {

  public int findLPSLength(String st) {
    return findLPSLengthRecursive(st, 0, st.length()-1);
  }

  private int findLPSLengthRecursive(String st, int startIndex, int endIndex) {
    if(startIndex > endIndex)
      return 0;

    //有一个元素的序列是一个长度为1的回文序列
    if(startIndex == endIndex)
      return 1;

    //选项1：序列头和尾的元素相同
    if(st.charAt(startIndex) == st.charAt(endIndex))
      return 2 + findLPSLengthRecursive(st, startIndex+1, endIndex-1);

    //选项2： 从开头或结尾跳过一个元素
    int c1 =  findLPSLengthRecursive(st, startIndex+1, endIndex);
    int c2 =  findLPSLengthRecursive(st, startIndex, endIndex-1);
    return Math.max(c1, c2);
  }

  public static void main(String[] args) {
    LPS lps = new LPS();
    System.out.println(lps.findLPSLength("abdbca"));
    System.out.println(lps.findLPSLength("cddpd"));
    System.out.println(lps.findLPSLength("pqr"));
  }
}

JavaScript

class LPS {
  findLPSLength(st) {
    return this.findLPSLengthRecursive(st, 0, st.length - 1);
  }

  findLPSLengthRecursive(st, startIndex, endIndex) {
    if (startIndex > endIndex) {
      return 0;
    }

    if (startIndex === endIndex) {
      return 1;
    }

    if (st.charAt(startIndex) === st.charAt(endIndex)) {
      return 2 + this.findLPSLengthRecursive(st, startIndex + 1, endIndex - 1);
    }

    const c1 = this.findLPSLengthRecursive(st, startIndex + 1, endIndex);
    const c2 = this.findLPSLengthRecursive(st, startIndex, endIndex - 1);
    return Math.max(c1, c2);
  }
}

const lps = new LPS();
console.log(lps.findLPSLength("abdbca"));
console.log(lps.findLPSLength("cddpd"));
console.log(lps.findLPSLength("pqr"));

Python

class LPS:
  def findLPSLength(self, st):
    return self.findLPSLengthRecursive(st, 0, len(st) - 1)

  def findLPSLengthRecursive(self, st, startIndex, endIndex):
    if startIndex > endIndex:
      return 0

    if startIndex == endIndex:
      return 1

    if st[startIndex] == st[endIndex]:
      return 2 + self.findLPSLengthRecursive(st, startIndex + 1, endIndex - 1)

    c1 = self.findLPSLengthRecursive(st, startIndex + 1, endIndex)
    c2 = self.findLPSLengthRecursive(st, startIndex, endIndex - 1)
    return max(c1, c2)

lps = LPS()
print(lps.findLPSLength("abdbca"))
print(lps.findLPSLength("cddpd"))
print(lps.findLPSLength("pqr"))

Go

package main

import "fmt"

type LPS struct{}

func (lps LPS) findLPSLength(st string) int {
	return lps.findLPSLengthRecursive(st, 0, len(st)-1)
}

func (lps LPS) findLPSLengthRecursive(st string, startIndex, endIndex int) int {
	if startIndex > endIndex {
		return 0
	}

	if startIndex == endIndex {
		return 1
	}

	if st[startIndex] == st[endIndex] {
		return 2 + lps.findLPSLengthRecursive(st, startIndex+1, endIndex-1)
	}

	c1 := lps.findLPSLengthRecursive(st, startIndex+1, endIndex)
	c2 := lps.findLPSLengthRecursive(st, startIndex, endIndex-1)
	if c1 > c2 {
		return c1
	}
	return c2
}

func main() {
	lps := LPS{}
	fmt.Println(lps.findLPSLength("abdbca"))
	fmt.Println(lps.findLPSLength("cddpd"))
	fmt.Println(lps.findLPSLength("pqr"))
}

自顶向下(备忘录)

Java

class LPS {

  public int findLPSLength(String st) {
    Integer[][] dp = new Integer[st.length()][st.length()];
    return findLPSLengthRecursive(dp, st, 0, st.length()-1);
  }

  private int findLPSLengthRecursive(Integer[][] dp, String st, int startIndex, int endIndex) {
    if(startIndex > endIndex)
      return 0;

    //有一个元素的序列是一个长度为1的回文序列
    if(startIndex == endIndex)
      return 1;

    if(dp[startIndex][endIndex] == null) {
      //选项1：序列头和尾的元素相同
      if(st.charAt(startIndex) == st.charAt(endIndex)) {
        dp[startIndex][endIndex] = 2 + findLPSLengthRecursive(dp, st, startIndex+1, endIndex-1);
      } else {
        //选项2： 从开头或结尾跳过一个元素
        int c1 =  findLPSLengthRecursive(dp, st, startIndex+1, endIndex);
        int c2 =  findLPSLengthRecursive(dp, st, startIndex, endIndex-1);
        dp[startIndex][endIndex] = Math.max(c1, c2);
      }
    }

    return dp[startIndex][endIndex];
  }

  public static void main(String[] args) {
    LPS lps = new LPS();
    System.out.println(lps.findLPSLength("abdbca"));
    System.out.println(lps.findLPSLength("cddpd"));
    System.out.println(lps.findLPSLength("pqr"));
  }
}

JavaScript

class LPS {
  findLPSLength(st) {
    const dp = Array.from({ length: st.length }, () => Array(st.length).fill(null));
    return this.findLPSLengthRecursive(dp, st, 0, st.length - 1);
  }

  findLPSLengthRecursive(dp, st, startIndex, endIndex) {
    if (startIndex > endIndex)
      return 0;

    if (startIndex === endIndex)
      return 1;

    if (dp[startIndex][endIndex] === null) {
      if (st[startIndex] === st[endIndex]) {
        dp[startIndex][endIndex] = 2 + this.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex - 1);
      } else {
        const c1 = this.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex);
        const c2 = this.findLPSLengthRecursive(dp, st, startIndex, endIndex - 1);
        dp[startIndex][endIndex] = Math.max(c1, c2);
      }
    }

    return dp[startIndex][endIndex];
  }
}

const lps = new LPS();
console.log(lps.findLPSLength("abdbca"));
console.log(lps.findLPSLength("cddpd"));
console.log(lps.findLPSLength("pqr"));

Python

class LPS:
  def findLPSLength(self, st):
    dp = [[None] * len(st) for _ in range(len(st))]
    return self.findLPSLengthRecursive(dp, st, 0, len(st) - 1)

  def findLPSLengthRecursive(self, dp, st, startIndex, endIndex):
    if startIndex > endIndex:
      return 0

    if startIndex == endIndex:
      return 1

    if dp[startIndex][endIndex] is None:
      if st[startIndex] == st[endIndex]:
        dp[startIndex][endIndex] = 2 + self.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex - 1)
      else:
        c1 = self.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex)
        c2 = self.findLPSLengthRecursive(dp, st, startIndex, endIndex - 1)
        dp[startIndex][endIndex] = max(c1, c2)

    return dp[startIndex][endIndex]

lps = LPS()
print(lps.findLPSLength("abdbca"))
print(lps.findLPSLength("cddpd"))
print(lps.findLPSLength("pqr"))

Go

package main

import (
	"fmt"
)

type LPS struct{}

func (lps *LPS) findLPSLength(st string) int {
	dp := make([][]int, len(st))
	for i := range dp {
		dp[i] = make([]int, len(st))
	}
	return lps.findLPSLengthRecursive(dp, st, 0, len(st)-1)
}

func (lps *LPS) findLPSLengthRecursive(dp [][]int, st string, startIndex, endIndex int) int {
	if startIndex > endIndex {
		return 0
	}

	if startIndex == endIndex {
		return 1
	}

	if dp[startIndex][endIndex] == 0 {
		if st[startIndex] == st[endIndex] {
			dp[startIndex][endIndex] = 2 + lps.findLPSLengthRecursive(dp, st, startIndex+1, endIndex-1)
		} else {
			c1 := lps.findLPSLengthRecursive(dp, st, startIndex+1, endIndex)
			c2 := lps.findLPSLengthRecursive(dp, st, startIndex, endIndex-1)
			dp[startIndex][endIndex] = max(c1, c2)
		}
	}

	return dp[startIndex][endIndex]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	lps := LPS{}
	fmt.Println(lps.findLPSLength("abdbca"))
	fmt.Println(lps.findLPSLength("cddpd"))
	fmt.Println(lps.findLPSLength("pqr"))
}

自底向上

Java

class LPS {

  public int findLPSLength(String st) {
    // dp[i][j]矩阵用于存储从索引i到索引j的最长回文子序列的长度
    int[][] dp = new int[st.length()][st.length()];

    // 每个只有一个元素的序列是一个长度为1的回文
    for (int i = 0; i < st.length(); i++)
      dp[i][i] = 1;

    for (int startIndex = st.length() - 1; startIndex >= 0; startIndex--) {
      for (int endIndex = startIndex + 1; endIndex < st.length(); endIndex++) {
        // case 1: 开头和结尾的元素相同
        if (st.charAt(startIndex) == st.charAt(endIndex)) {
          dp[startIndex][endIndex] = 2 + dp[startIndex + 1][endIndex - 1];
        } else { // case 2: 跳过在开头和结尾的元素
          dp[startIndex][endIndex] = Math.max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1]);
        }
      }
    }
    return dp[0][st.length() - 1];
  }

  public static void main(String[] args) {
    LPS lps = new LPS();
    System.out.println(lps.findLPSLength("abdbca"));
    System.out.println(lps.findLPSLength("cddpd"));
    System.out.println(lps.findLPSLength("pqr"));
  }
}

JavaScript

class LPS {
  findLPSLength(st) {
    const dp = Array(st.length)
      .fill(0)
      .map(() => Array(st.length).fill(0));

    for (let i = 0; i < st.length; i++) {
      dp[i][i] = 1;
    }

    for (let startIndex = st.length - 1; startIndex >= 0; startIndex--) {
      for (let endIndex = startIndex + 1; endIndex < st.length; endIndex++) {
        if (st[startIndex] === st[endIndex]) {
          dp[startIndex][endIndex] = 2 + dp[startIndex + 1][endIndex - 1];
        } else {
          dp[startIndex][endIndex] = Math.max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1]);
        }
      }
    }

    return dp[0][st.length - 1];
  }
}

const lps = new LPS();
console.log(lps.findLPSLength('abdbca'));
console.log(lps.findLPSLength('cddpd'));
console.log(lps.findLPSLength('pqr'));

Python

class LPS:
    def findLPSLength(self, st):
        dp = [[0] * len(st) for _ in range(len(st))]

        for i in range(len(st)):
            dp[i][i] = 1

        for startIndex in range(len(st) - 1, -1, -1):
            for endIndex in range(startIndex + 1, len(st)):
                if st[startIndex] == st[endIndex]:
                    dp[startIndex][endIndex] = 2 + dp[startIndex + 1][endIndex - 1]
                else:
                    dp[startIndex][endIndex] = max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1])

        return dp[0][len(st) - 1]


lps = LPS()
print(lps.findLPSLength("abdbca"))
print(lps.findLPSLength("cddpd"))
print(lps.findLPSLength("pqr"))

Go

package main

import "fmt"

type LPS struct{}

func (lps *LPS) findLPSLength(st string) int {
	dp := make([][]int, len(st))
	for i := range dp {
		dp[i] = make([]int, len(st))
	}

	for i := 0; i < len(st); i++ {
		dp[i][i] = 1
	}

	for startIndex := len(st) - 1; startIndex >= 0; startIndex-- {
		for endIndex := startIndex + 1; endIndex < len(st); endIndex++ {
			if st[startIndex] == st[endIndex] {
				dp[startIndex][endIndex] = 2 + dp[startIndex+1][endIndex-1]
			} else {
				dp[startIndex][endIndex] = max(dp[startIndex+1][endIndex], dp[startIndex][endIndex-1])
			}
		}
	}

	return dp[0][len(st)-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	lps := &LPS{}
	fmt.Println(lps.findLPSLength("abdbca"))
	fmt.Println(lps.findLPSLength("cddpd"))
	fmt.Println(lps.findLPSLength("pqr"))
}