动态规划（最大公共子序列）

客官°小女子只卖身不卖艺 2022-06-05 08:56 151阅读 0赞

> 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

例子：求两个字符串的最大公共子序列长度

> 一个字符串的子序列，是指从该字符串中去掉任意多个字符后剩下的字符在不改变顺序的情况下组成的新字符串。  
> 最长公共子序列，是指多个字符串可具有的长度最大的公共的子序列。

abcda和aca最大公共子序列为aca长度为3  
r a n d o m  
a 0 1 1 1 1 1  
n 0  
d 0  
r 1  
o 1  
i 1  
d 1

动态规划采用二维数组来标识中间计算结果，避免重复的计算来提高效率。  
推理公式：  
![这里写图片描述][SouthEast]  
代码 ：

//最大公共子序列（动态规划）
    public class LCS {
        public int findLCS(String A,String B){
            int n = A.length();
            int m = B.length();
            char[] a = A.toCharArray();
            char[] b = B.toCharArray();
            int [][] dp = new int[n][m];
            for(int i = 0;i<n;i++){
       //第一列
                if(a[i] == b[0]){
                    dp[i][0] = 1;
                    for(int j = i+1;j<n;j++){
                        dp[j][0] = 1;
                    }
                    break;
                }
            }
    
            for(int i = 0;i<m;i++){
       //第一行
                if(a[0] == b[i]){
                    dp[0][i] = 1;
                    for(int j = i+1;j<m;j++){
                        dp[0][j] = 1;
                    }
                    break;
                }
            }
            for(int i = 1;i<n;i++){
                for(int j = 1;j<m;j++){
                    if(a[i] == b[j]){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else{
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }
            for(int i = 0;i<n;i++){
                for(int j = 0;j<m;j++){
                    System.out.print(dp[i][j]+" ");
                }
                System.out.println();
            }
            return dp[n-1][m-1];
        }
    
        public static void main(String [] args){
            LCS lcs = new LCS();
            int findLCS = lcs.findLCS("androidma", "randommcac");
            System.out.println("最长子序列长度："+findLCS);
        }
    }

运算结果：

> 0 1 1 1 1 1 1 1 1 1  
> 0 1 2 2 2 2 2 2 2 2  
> 0 1 2 3 3 3 3 3 3 3  
> 1 1 2 3 3 3 3 3 3 3  
> 1 1 2 3 4 4 4 4 4 4  
> 1 1 2 3 4 4 4 4 4 4  
> 1 1 2 3 4 4 4 4 4 4  
> 1 1 2 3 4 5 5 5 5 5  
> 1 2 2 3 4 5 5 5 6 6  
> 最长子序列长度：6

![这里写图片描述][SouthEast 1]

[SouthEast]: /images/20220605/9a100824169b49fe96a999b025e54954.png
[SouthEast 1]: /images/20220605/d29e9917bc784dccb21fe67a6fa2d7ec.png