常见动态规划问题

程序员文章站 2023-12-26 12:41:27

...

定义：

动态规划（Dynamic Programmaing）是解决决策过程中最优化的数学方法。因为问题的多样性导致决策过程中的决策方法不同，所以动态规划没有统一的算法，不同问题要具体分析找出规律。

适用情况：

用DP要满足3个条件：

①最优子结构（一个最优的结构的子结构一定是最优的）

②无后向性（过去的决策不能影响未来的决策，之前是怎么到达这个状态的我不管，我只管在这个状态下，也就是说某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响）

③子问题重叠（用空间换时间，解决冗余，前面算过的记住）

问题：

1.最长公共子序列（Longest Common Sequence）

对于序列S和T，求它们的最长公共子序列。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。求出一个即可。

解法：

　　对于X[1...m]和Y[1...n]，它们的任意一个lcs是Z[1...k]。

　　(1)如果X[m]=Y[n]，那么Z[k]=X[m]=Y[n],且Z[1...k-1]是X[1...m-1]和Y[1...n-1]的一个lcs；

　　(2)如果X[m]!=Y[n]，那么Z[k]!=X[m]时Z是X[1...m-1]和Y的一个lcs；

　　(3)如果X[m]!=Y[n]，那么Z[k]!=Y[n]时Z是X和Y[1...n-1]的一个lcs；

所以可以写出状态转移方程：c[i][j] = c[i-1][j-1] + 1; A[i-1] == B[j-1]

c[i][j] = c[i][j-1]; c[i][j-1] > c[i-1][j]

c[i][j] = c[i-1][j]; c[i-1][j] > c[i][j-1]

边界条件： c[0...i][0] = 0; c[0][0...j] = 0;

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        vector< vector<int> > c(n+1,vector<int>(m+1,0));
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                if(A[i-1]==B[j-1])
                {
                    c[i][j] = c[i-1][j-1] + 1;
                }
                else
                {
                    c[i][j] = max(c[i-1][j],c[i][j-1]);
                }
            }
        }
        return c[n][m];
    }
};

扩展：求长度容易，怎么求有哪些LCS呢？

常见动态规划问题

从上图可以看到，从（7，6）出发找到状态是左上的位置连起来就是一个LCS，可以利用回溯来找到，具体办法就是比较c[i][j]和c[i-1][j] c[i][j-1]的值

如果c[i-1][j] == c[i][j] && c[i][j-1] != c[i][j] 那么 i--

如果c[i][j-1] == c[i][j] && c[i-1][j] != c[i][j] 那么 j--

如果c[i-1][j] == c[i][j] && c[i][j-1] == c[i][j] 那么i--和j--选一个，弄完之后再回溯另外一个

否则找到一个左上的状态字符 A[i-1]；i--;j--;

常见动态规划问题