题解 | 最长公共子序列

package main

import (
	"fmt"
)

func main() {
	var str1 string
	var str2 string
	for {
		n, _ := fmt.Scan(&str1, &str2)
		if n == 0 {
			break
		} else {
			dp := make([][]int, len(str1)+1)
			for i := 0; i < len(dp); i++ {
				dp[i] = make([]int, len(str2)+1)
			}
			for i := 1; i < len(dp); i++ {
				for j := 1; j < len(dp[i]); j++ {
					if str1[i-1] == str2[j-1] {
						dp[i][j] = dp[i-1][j-1] + 1
					} else {
						dp[i][j] = max(dp[i-1][j], dp[i][j-1])
					}
				}
			}
			i, j := len(str1), len(str2)
			k := dp[i][j]
			res := make([]byte, dp[i][j])
		  	// 利用已有dp 反着找数据
			for k>0 {
				if str1[i-1] == str2[j-1] { 
				  	// str1[i-1] == str2[j-1]， 
				   // 原来 dp[i][j] = dp[i-1][j-1] + 1
				  // 反着操作，
					res[k-1] = str1[i-1]
					k--
					i--
					j--
				// dp[i][j] = max(dp[i-1][j], dp[i][j-1])
				// dp[i-1][j]>dp[i][j-1] i--
				// dp[i-1][j]<=dp[i][j-1] j--
				} else if dp[i-1][j] > dp[i][j-1] {
					i--
				} else {
					j--
				}
			}
			if len(res) > 0 {
				fmt.Println(string(res))
			} else {
				fmt.Println(-1)
			}
		}
	}
}

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