UVA.10066 The Twin Towers (DP LCS)

題意分析

有2座塔，分別由不同長度的石塊組成。現在要求移走一些石塊，使得這2座塔的高度相同，求高度最大是多少。

問題的實質可以轉化為LCS（最長公共子序列）問題。 推薦一篇寫的比較好的博文： 動態規劃求解最長公共子序列（LCS）

核心的狀態轉移方程： if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] +1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

代碼總覽