动态规划永利游戏平台

2019-11-15 03:47

算法学习 - 最长公共子序列（LCS）C++实现

一个字符串的子串是字符串中连续的一个序列，而一个字符串的子序列是字符串中保持相对位置的字符序列，譬如，"adi"可以使字符串"abcdefghi"的子序列但不是子串。这也就决定了在解这两种"LCS"问题上的一些区别。
Longest-Common-Substring和Longest-Common-Subsequence是不一样的。

动态规划（Dynamic Programming）

本文包括：

动态规划定义
状态转移方程
动态规划算法步骤
最长非降子序列（LIS）
最大乘积子串
Unique Paths
Unique Paths II
Minimum Path Sum
Triangle
最长公共自序列（LCS）
编辑距离
交替字符串
矩阵链乘积

前文引自：http://www.hawstein.com/posts/dp-novice-to-advanced.html

最长公共子序列

最长公共子序列的问题很简单，就是在两个字符串中找到最长的子序列，这里明确两个含义：

子串：表示连续的一串字符。子序列：表示不连续的一串字符。

所以这里要查找的是不连续的最长子序列，

参考：
wiki-动态规划
何海涛微博

1、什么是动态规划，我们要如何描述它？

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。
首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。

动态规划

这里为什么要使用动态规划可以说一下，简单来说动态规划是为了降低时间复杂度的一种算法，申请一个额外空间，来保存每一个步骤的结果，最后从这些结果中找到最优的解。

这里有个问题就是：一般来说，当前的最优解，只与当前时刻和上一时刻有关系，和其他时刻没有关系，这样才能让动态规划发生作用，降低复杂度。

动态规划DP

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有[重叠子问题]和[最优子结构]性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其[记忆化]存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈[指数增长]时特别有用。

DP问题有几个典型应用：
解整数背包问题：设有n件物品，每件价值记为Pi，每件体积记为Vi，用一个最大容积为Vmax的背包，求装入物品的最大价值。用一个数组f[i,j]表示取i件商品填充一个容积为j的背包的最大价值，显然问题的解就是f[n,Vmax].
f[i,j]=

  f[i-1,j] {j<Vi}
  max{f[i-1,j],f[i,j-Vi]+Pi} {j>=Vi}
  0 {i=0 OR j=0}

对于特例01背包问题（即每件物品最多放1件，否则不放入）的问题，状态转移方程：

f[i,j]=

  f[i-1,j] {j<Vi}
  max{f[i-1,j],f[i-1,j-Vi]+Pi} {j>=Vi}
  0 {i=0 OR j=0}

WIKI上举的第一个例子是Fibonacci数列，普通的递归求法会重复计算很多次前面的值因而效率很低，所以我们可以从低位算起。这样就可以利用前面的值。

到目前为止我对DP的理解就是，每一步的结果都与上一步有关。

2、“状态”代表什么及如何找到它？

“状态”用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚，跳过直接上例子。
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)
首先我们思考一个问题，如何用最少的硬币凑够i元(i<11)？为什么要这么问呢？两个原因：1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。 2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。
好了，让我们从最小的i开始吧。当i=0，即我们需要多少个硬币来凑够0元。由于1，3，5都大于0，即没有比0小的币值，因此凑够0元我们最少需要0个硬币。 (这个分析很傻是不是？别着急，这个思路有利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。”会比较方便，如果一直用纯文字来表述，不出一会儿你就会觉得很绕了。
那么，我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。当i=1时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够0元即可，而这个是已经知道答案的，即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。当i=2时，仍然只有面值为1的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2。
一直到这里，你都可能会觉得，好无聊，感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币！耐心点，让我们看看i=3时的情况。当i=3时，我们能用的硬币就有两种了：1元的和3元的( 5元的仍然没用，因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬币有两种，我就有两种方案。如果我拿了一个1元的硬币，我的目标就变为了：凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。这个方案说的是，我拿3个1元的硬币；第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 这个方案说的是，我拿1个3元的硬币。
好了，这两种方案哪种更优呢？记得我们可是要用最少的硬币数量来凑够3元的。所以，选择d(3)=1，怎么来的呢？具体是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。
从以上的文字中，我们要抽出动态规划里非常重要的两个概念：状态和状态转移方程。
上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的”状态”，这个状态是怎么找出来的呢？我在另一篇文章动态规划之背包问题(一)中写过：根据子问题定义状态。你找到子问题，状态也就浮出水面了。最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币。
那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。没错，它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下，
```
  d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;
```
伪代码：
依次计算，可以计算出11元至少要3枚硬币。

分析LCS

其实LCS看起来很麻烦，找不到思路，如果暴力破解可能要O(n^4)了，而这个题目使用动态规划的思想也非常简单，为何相比之前的问题不好找思路呢？

是因为之前的动态规划问题例如：背包问题，生产线问题，都是一维数组空间内的结果，规划到一个线性时间内，而这个题目需要O(m*n)的时间复杂度和空间复杂度。

所以其实就是进行m*n次对比，每次保存当前的最优解，就可以了。

LCS（longest common subsequence）

我们有两个字符串，现在求两个字符串的最长公共子序列（注：这里的要求不包括字符必须连续）
例：abdhgf和dadchgm的LCS就是adhg
这种问题确实不好做，一般的思路解决太复杂了。如果用遍历的方式，不想等的时候往前移动，相等的话，看后面的是否相等，后面的一个也存在之前的情况。。

但是我们也可以假设我们已经有一段字符串满足相同的子序列了，那么我们关心当前的这一个就可以了。

我们假设两个字符串的长度为m，n；LCS的长度为k；并且假设LCS里面的所有字符都是满足条件的
并且假设前k个都满足情况了，我们讨论第k个：

设Xm={x0,x1,…xm-1}和Yn={y0,y1,…,yn-1}为两个字符串，而Zk={z0,z1,…zk-1}是它们的LCS，则：

如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的LCS；
如果xm-1≠yn-1，那么当zk-1≠xm-1时Z是Xm-1和Y的LCS；
如果xm-1≠yn-1，那么当zk-1≠yn-1时Z是Yn-1和X的LCS

注：这个关系大家多想一想，是最重要的部分。
如果觉得上面的文字有干扰的话，可以自己去理解。

上面的关系式实际上是逆推，即我们假设已经有了LCS，我们去找LCS在两个字符串里面的位置。

我觉得很重要的一点就是，我们只关心这一步（和上一步的关系），至于上一步也不满足的话，那就是递归的事情了。这样想能简化思路！

**性质大家可以反证法证明一下，如果不能理解，可以举个例子试一下，LCS里面的字符肯定会出现在x，y里面，如果x，y的最后面是无关的字符，后面的两个条件就可以逐步把无关的删除掉；
其实后面两个条件就是去掉无关字符的过程，讨论的都是当x！=y的情况。
**

由上面的三种情况：

我们可以得出如下的思路：求两字符串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS，

如果xm-1=yn-1，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm-1（ yn-1）即可；
如果xm-1≠yn-1，我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且这两个LCS中较长的一个为X和Y的LCS

这就是DP的特点吧，每一步的情况都有两种（多种），你看着办吧。

如果我们记字符串Xi和Yj的LCS的长度为c[i,j]，我们可以递归地求c[i,j]：

0, if i<0 or j<0
c[i-1,j-1]+1 ,if i,j>=0 and xi=xj
max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj

根据这个思路，我们创建一个矩阵lcs_length来记录对应的i，j的值，之所以这样是为了避免类似于Fibonacci里面的重复求值的问题，以及方便输出。
在下面的代码里面，还创建了一个lcs_dir的矩阵，这个也是为了保存每一次值的来源，方便我们打印的时候知道取哪个值。

这个程序的主干部分是这样的：
矩阵的横列是str2，竖列是str1
结合上面的实例，我们得到的矩阵是这样的：

str	a	b	d	h	g	f
d	0	0	1	0	0	0
a	1	1	1	1	1	1
d	1	1	2	2	2	2
c	0	1	2	2	2	2
h	0	1	2	3	3	3
g	0	1	2	3	4	4

下面是代码：

//c[i,k]=
// 0, if i<0 or j<0
// c[i - 1, j - 1] + 1, if i, j >= 0 and xi = xj
// max(c[i, j - 1], c[i - 1, j] if i, j >= 0 and xi≠xj
#include <iostream>

enum dir {kinit=0,kup,kleftup,kleft};//c[i,j] comes from 3 directions

//we have a matrix holding value,another holding the direction
int lcs(char* str1,char* str2)
{
    if (!str1 || !str2)
        return;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    if (!len1 || !len2)
        return 0;

    unsigned int i, j;
    int** lcs_len = (int**)(new int[len1]);
    for (i = 0; i < len1; i++)
        lcs_len[i] = (int*)new int[len2];
    for (i = 0; i < len1; i++)
        for (j = 0; j < len2; j++)
            lcs_len[i][j] = 0;

    int** lcs_dir = (int**)(new int[len1]);
    for (i = 0; i < len1; i++)
        lcs_dir[i] = (int*)new int[len2];
    for (i = 0; i < len1; i++)
        for (j = 0; j < len2; j++)
            lcs_dir[i][j] =kinit ;

    //core: detect every unit
    for (i = 0; i < len1; i++)
        for (j = 0; j < len2; j++)
        {
            if (i == 0 || j == 0)//the begin of common string
            {
                if (str1[i] == str2[j])
                {
                    lcs_len[i][j] = 1;
                    lcs_dir[i][j] = kleftup;
                }
                else
                    lcs_len[i][j] = 0;

            }
            else if (str1[i] == str2[j])
            {
                lcs_len[i][j] = lcs_len[i - 1][j - 1] + 1;//case 1
                lcs_dir[i][j] = kleftup;
            }
            else if (lcs_len[i - 1][j] > lcs_len[i][j - 1])
            {
                lcs_len[i][j] = lcs_len[i - 1][j] ;
                lcs_dir[i][j] = kup;
            }
            else
            {
                lcs_len[i][j] = lcs_len[i][j-1] ;
                lcs_dir[i][j] = kleft;
            }
        }
    return lcs_len[len1 - 1][len2 - 1];
}

然后我们根据得到的矩阵打印：
只需要打印方向矩阵里面，方向标识为leftup的字符，其它的根据方向标识来移动。
既然这样的话，我们可以用递归的方式打印，简化代码量：

//only lcs_dir=kleftup are to be printed
void print_path(int**lcs_dir, char* str1, char* str2, size_t row, size_t col)
{
    if (!str1 || !str2)
        return;
    size_t len1 = strlen(str1);
    size_t len2 = strlen(str2);

    if (len1 == 0 || len2 == 0 || !(row < len1&&col < len2))
        return;

    if (lcs_dir[row][col] == kleftup)
    {
        if (row > 0 && col > 0)
            print_path(lcs_dir, str1, str2, row - 1, col - 1);
        std::cout << str1[row];
    }
    if (lcs_dir[row][col]==kleft)
        print_path(lcs_dir, str1, str2, row , col - 1);
    if (lcs_dir[row][col] == kup)
        print_path(lcs_dir, str1, str2, row-1, col );
}

测试了一下没问题的。

总结一下吧，关于动态规划这个概念大家不要太纠结，其实重心在于如何找出规律!

3、DP 算法步骤

动态规划算法一般用来求解最优化问题，当问题有很多可行解，而题目要求寻找这些解当中的“最大值”/“最小值”时，通常可以采用DP。
动态规划算法与分治法相似，都是通过组合子问题的解来求解原问题。所不同的是，动态规划应用于子问题重叠的情况，在递归求解子问题的时候，一些子子问题可能是相同的，这种情况下，分治法会反复地计算同样的子问题，而动态规划对于相同的子问题只计算一次。

动态规划算法的设计步骤：

  1、刻画最优解的结构特征（寻找最优子结构）
  2、递归地定义最优解的值（确定递归公式，动态规划法的重点就是这个）
  3、计算最优解的值（有两种方法：带备忘录自顶向下法、自底向上法）
  4、利用计算出的信息构造一个最优解（通常是将具体的最优解输出）

最优子结构：问题的最优解包含的子问题的解相对于子问题而言也是最优的。
并非所有组合优化问题都具有最优子结构特性。

代码实现分析

这里有个问题，就是我们需要的结果仅仅是长度？还是包括这个序列串一起输出。

看下面图：

永利游戏平台 1

这里可以看到，我们构造的一个i*j的矩阵，这个矩阵里的内容不但包括数值（当前结果的最优解），还包括一个方向箭头，这个代表了我们回溯的时候，需要行走的方向。< 喎?" target="_blank" class="keylink">vcD4NCjxwPsv50tTO0sPH1eLA77GjtObBvbj21rWjrL/J0tTKudPDwb249rb+zqy+2NXzo6zSsr/J0tTKudPD0ru49r3hubnM5b7Y1fOhozwvcD4NCjxoMSBpZD0="解法分析">解法分析

其实这个题目在动态规划来理解，也非常简单。一个状态转移函数。

永利游戏平台 2

这个非常好理解，其中一个字符串为0的时候，那么肯定是0了。

当两个字符相等的时候，这个时候很好理解，举例来说：

abcd 和 adcd,在遍历c的时候，发现前面只有a相等了，也就是1.
那么c相等，也就是abc和adc在匹配的时候，一定比ab和ad的长度大1，这个1就是c相等么。也就是相等的时候，是比c[i-1][j-1]大1的。

下一个更好理解了，如果不相等，肯定就是找到上一个时刻对比最大的么。

4、最长非降子序列（LIS）

问题描述：

一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。
(讲DP基本都会讲到的一个问题LIS：longest increasing subsequence)
思路：

假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度，其中i<N，那么上面的问题变成了原问题的一个子问题(问题规模变小了，你可以让i=1,2,3等来分析)

然后我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。

如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。

OK，状态找到了，下一步找出状态转移方程。
可以举个例子，然后求出前面几项，找出递推规律

d(i)可以用下面的状态转移方程得到：
```
  d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
```

Python 代码：

  def LIS(A):
      d = [0 for i in range(len(A))]
      for i in range(len(A)):
          d[i] = 1   # 就算前面所有元素都比当前大，那么至少可以包含自身，所以长度默认值为1
          for j in range(i):
              if A[i] >= A[j] and d[j]+1 > d[i]:
                  d[i] = d[j] + 1
      return max(d)

  A = [5, 3, 4, 8, 6, 7]
  print(LIS(A))

代码

这个代码只输出了LCS的长度，而结果数组的方向我已经存储好了，想要遍历的，直接从后向前遍历数组就好了。

//
//  main.cpp
//  LCS
//
//  最长公共子序列(LCS)
//
//  Created by Alps on 15/8/23.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 

using namespace std;

/*
* 这里可以不定义长度，输入的字符串用string存储，然后利用string.c_str()来对字符串进行数组转化。 我这里为了方便没有这样做。
*/
#ifndef MAX_LENGTH
#define MAX_LENGTH 15 //定义字符串最大长度
#endif

int MaxNum(int firstNum, int secondNum){
    return firstNum > secondNum ? firstNum : secondNum;
}

//定义数组结构体
struct matrix{
    int num;
    int direct;
};

typedef matrix Matrix;

int LCS(char *strA, char *strB, int lengthA, int lengthB, Matrix *resultMatrix[]){
    if (lengthA == 0 || lengthB == 0) {
        return 0;
    }
    for (int i = 0; i < lengthA; i++) {
        for (int j = 0; j < lengthB; j++) {
            resultMatrix[i][j].num = 0; //设置所有默认的最长为0
            resultMatrix[i][j].direct = 1; //所有默认方向变成上 0斜上，1上，-1左
        }
    }

    for (int i = 0; i < lengthA; i++) {
        for (int j = 0; j < lengthB; j++) {
            if (strA[i] == strB[j]) {
                resultMatrix[i+1][j+1].num = resultMatrix[i][j].num + 1;
                resultMatrix[i+1][j+1].direct = 0;
            }else{
                resultMatrix[i+1][j+1].num = MaxNum(resultMatrix[i+1][j].num, resultMatrix[i][j+1].num);
                resultMatrix[i+1][j+1].direct = resultMatrix[i+1][j].num > resultMatrix[i][j+1].num ? 1 : -1;
            }
        }
    }
    return resultMatrix[lengthA][lengthB].num;
}

int main(int argc, const char * argv[]) {
    char *strA = (char*)malloc(sizeof(char) * MAX_LENGTH);
    char *strB = (char*)malloc(sizeof(char) * MAX_LENGTH);
    scanf(%s,strA);
    scanf(%s,strB);
    int lengthA = (int)strlen(strA);
    int lengthB = (int)strlen(strB);
    Matrix *resultMatrix[lengthA+1];
    for (int i = 0; i <= lengthA; i++) {
        resultMatrix[i] = (Matrix*)malloc(sizeof(struct matrix)* (lengthB+1));
    }

    int max = LCS(strA, strB, lengthA, lengthB, resultMatrix);
    printf(%d
,max);
    std::cout << Hello, World!
;
    return 0;
}

以上。©Alps1992

- 最长公共子序列（LCS）C++实现最长公共子序列最长公共子序列的问题很简单，就是在两个字符串中找到最长的子序列，这里明...

另一个解法：利用LCS思想（第9点）

构造一个新序列，B，它是对A进行降序排列而得。
此时求最长非增子序列，调用LCS-LENGTH即可求出A与B的最长公共子序列，这个序列就是最后的解。

5、最大乘积子串

题目描述：

给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。
也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是连续的。
思路：

因为有正有负，下次要处理的 a[i] 可能是负，所以每次都要存储最小的子串乘积值，负负得正，得出的结果有可能还更大。

递推方程：

  maxend = max(max(maxend * a[i], minend * a[i]), a[i]);
  minend = min(min(maxend * a[i], minend * a[i]), a[i]);

Python 代码：

  def maxProductSubstring(a):
      maxend, minend, maxresult = a[0], a[0], a[0]
      for i in range(1,len(A)):
          maxend = max(max(maxend * a[i], minend * a[i]), a[i])
          minend = min(min(maxend * a[i], minend * a[i]), a[i])
          maxresult = max(maxend, maxresult)
      return maxresult

  A = [-2.5, 4, 0, 3, 0.5, 8, -1]
  print(maxProductSubstring(A))

6、Unique Paths

Leetcode:62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Solution：

  class Solution(object):
      def uniquePaths(self, m, n):
          """
          :type m: int
          :type n: int
          :rtype: int
          """
          c = [[0 for i in range(n+1)] for i in range(m+1)]
          for i in range(n+1):
              c[0][i] = 0
          for i in range(m+1):
              c[i][0] = 0
          for i in range(1, m+1):
              for j in range(1, n+1):
                  if i == 1 and j == 1:
                      c[i][j] = 1
                  else:
                      c[i][j] = c[i-1][j] + c[i][j-1]
          return c[i][j]

  sol = Solution()
  print(sol.uniquePaths(1, 1))

7、Unique Paths II

Leetcode:63. Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

solution:

  class Solution(object):
      def uniquePathsWithObstacles(self, obstacleGrid):
          """
          :type obstacleGrid: List[List[int]]
          :rtype: int
          """

          m = len(obstacleGrid)
          n = len(obstacleGrid[0])
          dp = [[0 for i in range(n+1)] for i in range(m+1)]
          dp[1][1] = 1
          for i in range(1, m+1):
              for j in range(1, n+1):
                  if obstacleGrid[i-1][j-1] == 1:
                      dp[i][j] = 0
                  elif i == 1 and j == 1:
                      dp[1][1] = 1
                  else:
                      dp[i][j] = dp[i-1][j] + dp[i][j-1]

          return dp[m][n]

  sol = Solution
  obstacleGrid = [
      [0, 0, 0],
      [0, 1, 0],
      [0, 0, 0]
  ]
  print(sol.uniquePathsWithObstacles(sol, obstacleGrid))

8、Minimum Path Sum

Leetcode:64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers,

find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

solution:

  class Solution(object):
      def minPathSum(self, grid):
          """
          :type grid: List[List[int]]
          :rtype: int
          """
          m = len(grid)
          if m > 0 and len(grid[0]) > 0:
              n = len(grid[0])
          else:
              return 0

          dp = [[0 for i in range(n+1)] for i in range(m+1)]
          for i in range(m+1):
              dp[i][0] = float('inf')
          for i in range(n+1):
              dp[0][i] = float('inf')
          dp[1][1] = grid[0][0]
          for i in range(1, m+1):
              for j in range(1, n+1):
                  if i == 1 and j == 1:
                      dp[i][j] = grid[i-1][j-1]
                  elif dp[i-1][j] < dp[i][j-1]:
                      dp[i][j] = dp[i-1][j] + grid[i-1][j-1]
                  else:
                      dp[i][j] = dp[i][j-1] + grid[i-1][j-1]
          return dp[m][n]

9、Triangle

Leetcode:120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
```
  [
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
  ]
```
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

第一次尝试：

  class Solution(object):
      def minimumTotal(self, triangle):
          """
          :type triangle: List[List[int]]
          :rtype: int
          """
          length = len(triangle)
          minSum = triangle[0][0]
          index = 0
          for i in range(1, length):
              if triangle[i][index] < triangle[i][index+1]:
                  minSum += triangle[i][index]
              else:
                  minSum += triangle[i][index+1]
                  index += 1
          return minSum

解释：
有点类似于贪心，每一步都寻找最优的，但是却没想到，全局最优可能是另外一种情况，比如下面的测试用例：

  Submission Result: Wrong Answer More Details 

  Input:
  [[-1],[2,3],[1,-1,-3]]
  Output:
  0
  Expected:
  -1

很明显，按照我的程序，走法是：-1 2 -1 = 0。
但是其实最优解是 -1 3 -3 = -1。

需要辅助空间 O(n^2) 的 DP 解法：

  '''
      extra space: O(n^2)
      using 'top to bottom' thought
  '''
  def minimumTotal(self, triangle):
      """
      :type triangle: List[List[int]]
      :rtype: int
      """
      length = len(triangle)
      dp = [[0 for i in range(j+1)] for j in range(length)] # dp[i][j] means element of row i column j is the last one of the min_path
      dp[0][0] = triangle[0][0]
      for i in range(1, length):
          for j in range(i+1):
              if j == 0:
                  dp[i][j] = dp[i-1][j] + triangle[i][j]
              elif j == i:
                  dp[i][j] = dp[i-1][j-1] + triangle[i][j]
              elif dp[i-1][j] < dp[i-1][j-1]:
                  dp[i][j] = dp[i-1][j] + triangle[i][j]
              else:
                  dp[i][j] = dp[i-1][j-1] + triangle[i][j]
      return min(dp[length-1])

理解不难，同样是构建二维数组，dp[i][j] 的意思是以 triangle[i][j] 结尾的最小路径和。这其实就是带备忘录的自顶向下办法。

需要辅助空间 O(n) 的 DP 解法（推荐！）：

  '''
      extra space: O(n)
      using 'bottom to top' thought
  '''
  def minimumTotal_bottomtotop(self, triangle):
      """
      :type triangle: List[List[int]]
      :rtype: int
      """
      length = len(triangle)
      dp = triangle[length-1]
      for i in range(length-2, -1, -1):
          for j in range(i+1):
              dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
      return dp[0]

这种办法是从底往上，dp 只是一维数组，在每层操作时，仅记录该层的各元素结尾的最小路径和，并且路径是从底往上。在处理不同层时，dp 根据下一层的计算结果算出当前层的值，所以一直在变。辅助空间只有 O(n)。

10、最长公共子序列（LCS）

最长公共子序列（Longest Common Subsequence）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。
LCS 问题可以用动态规划思想完美解决：
- 设二维数组 f[i][j] 表示：数组 X 的前 i 位与数组 Y 的前 j 位的最长公共子序列的长度
- 则有：
```
f[i][j] = same(1,1)
f[i][j] = max{f[i-1][j-1] + same(i,j), f[i-1][j], f[i][j-1]}
```
- 其中，same(a,b) 表示：当 X 的第 a 位与 Y的第 b 位完全相同时为“1”，否则为“0”。

综上，可以总结出如下的算法，用B[i,j]来作标记，

  用"↖"表示序列 X 和 Y 的当前最后两项 x[i] 和  y[j] 相等；
  用“↑”表示选择时不考虑 x[i]，即 f[i][j] = f[i-1][j];
  用“←”表示选择时不考虑 y[j]，即 f[i][j] = f[i][j-1]

  LCS_LENGTH(X, Y):
  for i := 1 to m
      C[i,0] := 0
  for j := 1 to n
      C[0,j] := 0
  for i := 1 to m
      for j := 1 to n
          if X[i] = Y[j]
              C[i,j] := C[i-1,j-1] + 1
              B[i,j] := "↖"
          else if C[i-1,j] >= C[i, j-1]
              C[i,j] := C[i-1,j]
              B[i,j] := "↑"
          else
              C[i,j] := C[i,j-1]
              B[i,j] : "←"

为了更加直观，这里用图表形象给出：

Python 代码（A表示↖，T表示↑，L表示←）：

  def LCS_LENGTH(X, Y):
      m = len(X)
      n = len(Y)
      c = [[0 for i in range(n+1)] for i in range(m+1)]
      b = [[0 for i in range(n)] for i in range(m)]
      for i in range(1, m + 1):
          for j in range(1, n + 1):
              if X[i-1] == Y[j-1]:
                  c[i][j] = c[i-1][j-1] + 1
                  b[i-1][j-1] = "A"
              elif c[i-1][j] >= c[i][j-1]:
                  c[i][j] = c[i-1][j]
                  b[i-1][j-1] = "T"
              else:
                  c[i][j] = c[i][j-1]
                  b[i-1][j-1] = "L"
      return c, b

      def print_lcs(b, X, i, j):
          if i == -1 or j == -1:
              return
          if b[i][j] == "A":
              print_lcs(b, X, i-1, j-1)
              print(X[i])
          elif b[i][j] == "T":
              print_lcs(b, X, i-1, j)
          else:
              print_lcs(b, X, i, j-1)
          return

      Y = "BDCABA"
      X = "ABCBDAB"
      c, b = LCS_LENGTH(X, Y)
      print_lcs(b, X, len(X)-1, len(Y)-1)

代码细节：
- 创建二维数组，并且不会出现引用的问题（引用问题是一改就改了多处）
```
c = [[0 for i in range(n+1)] for i in range(m+1)]
```
- b 是辅助的一个二维数组（表），用来指示当前的路径选择（走对角A，还是走上T，还是走左L），实际上，《算法导论》中也明确指出这里可以省略，进而在 print_lcs 过程中做比较，这样可以节省辅助空间，但是这样比较浅显易懂
  
  2017924-LCSb
- 构造完表后，就可以调用 print_lcs 过程来得到路径了，在过程中使用了递归的思想，并且最后输出的顺序是从字符串的左边到右边的
```
"C:Program FilesPython36python.exe" D:/PythonProject/DataStructure-Algorithm/DynamicProgramming/LCS.py
B
C
B
A

Process finished with exit code 0
```

11、编辑距离

题目描述：

给定一个源串和目标串，能够对源串进行如下操作：
1. 在给定位置上插入一个字符
2. 替换任意字符
3. 删除任意字符
写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。
思路：

动态规划，构建二维数组，注意二维数组的第0行和第0列不是全0的。

可以想象，如果source 为空，想要转换为 target，则肯定要执行 len(target) = n 次操作，所以dp[i][j]赋初值时要注意这点。

递推方程：

  //dp[i,j]表示表示源串S[0…i] 和目标串T[0…j] 的最短编辑距离
  dp[i,j] = min {dp[i-1,j]+1, dp[i,j-1]+1, dp[i-1,j-1] + (s[i] == t[j] ? 0 : 1) }
  //分别表示：删除1个，添加1个，替换1个（相同就不用替换）。

解释：
- 插入是A在和B的前j-1个比，然后再在A的基础上进行插入一个字符，插入的字符是B的第j位，所以插入的代价是dp[i][j-1]+1
- 删除是A的前i-1个和B的j个比，因为把A删除了一个字符，所以删除的代价是dp[i-1][j]+1
- 替换是A的前i-1个和B的j-1个比，然后把A的第i位变成B的第j位。所以编辑的代价是dp[i-1][j-1]+1

python 代码：

  def editDistance(source, target):
      m = len(source)
      n = len(target)

      dp = [[0 for i in range(n+1)] for i in range(m+1)]
      for i in range(n+1):
          dp[0][i] = i
      for i in range(m+1):
          dp[i][0] = i

      for i in range(1, m+1):
          for j in range(1, n+1):
              if source[i-1] == target[j-1]:
                  dp[i][j] = dp[i-1][j-1]
              else:
                  dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1
      return dp[m][n]

  source = "abc"
  target = "axxxbxxxc"
  print(editDistance(source, target))

12、交替字符串

Leetcode: 97. Interleaving String
题目描述：

输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，

例如当s1 = “aabcc”，s2 = “dbbca”，s3 = “aadbbcbcac”时，则输出true，但如果s3=“accabdbbca”，则输出false。
思路：

多个字符串做“比较”的问题，大多都可以用DP求解。

构建二维数组，一般其规模为：(m+1)*(n+1)。

令dp[i][j]代表s3[0...i+j-1]是否由s1[0...i-1]和s2[0...j-1]的字符组成。

自然，我们的想法是遍历s3中的每个元素，然而要如何找到递推关系呢？

因为只需要输出true或false，那么我们可以只计算true的情形，其余情况全是false。

假设dp[i-1][j]为true，那么dp[i][j]为true的条件就是s1[i-1]是否等于s3[i+j-1]。
假设dp[i][j-1]为true，那么dp[i][j]为true的条件就是s2[j-1]是否等于s3[i+j-1]。

由此递推关系就可以求出：

  dp[i][j]= (dp[i][j-1]  && str2[j-1]==str3[i+j-1])  || (dp[i-1][j]   && str1[i-1]==str3[i+j-1])

Python 代码：

  def isInterleave(s1, s2, s3):
      m = len(s1)
      n = len(s2)
      k = len(s3)
      if k != m + n:
          return False
      dp = [[False for i in range(n + 1)] for i in range(m + 1)]
      dp[0][0] = True
      # if s1[0] == s3[0]:
      #     dp[1][0] = True
      # if s2[0] == s3[0]:
      #     dp[0][1] = True
      for i in range(m+1):
          for j in range(n+1):
              if i != 0 or j != 0:
                  if dp[i-1][j] is True and s1[i-1] == s3[i+j-1]:
                      dp[i][j] = True
                  elif dp[i][j-1] is True and s2[j-1] == s3[i+j-1]:
                      dp[i][j] = True
                  else:
                      dp[i][j] = False
      return dp[i][j]

  s1 = "xyz"
  s2 = "abc"
  s3 = "xyzabc"
  print(isInterleave(s1, s2, s3))

13、矩阵链乘积

矩阵链乘积（英语：Matrix chain multiplication，或Matrix Chain Ordering Problem，MOCP）是可用动态规划解决的最佳化问题。给定一序列矩阵，期望求出相乘这些矩阵的最有效方法。此问题并不是真的去执行其乘法，而只是决定执行乘法的顺序而已。
因为矩阵乘法具有结合律，所有其运算顺序有很多种选择。换句话说，不论如何括号其乘积，最后结果都会是一样的。例如，若有四个矩阵ABCD,将可以有：
```
  ABCD = (AB)(CD) = A(BC)D = AB(CD) ...
```
但括号其乘积的顺序是会影响到需计算乘积所需简单算术的数目，假定各矩阵维数分别为 10x100 100x5 5x50，如果按 ((AB)C) 的加括号方式，要执行7500次标量乘法，而按(A(BC))的加括号方式，要执行75000次标量乘法。
那要如何决定n个矩阵相乘的最佳顺序呢？可以比较每一顺序的运算量（使用蛮力），但这将需要时间O(2^n)，是一种非常慢且对大n不实在的方法。那解决方法，如我们将看到的，是将问题分成一套相关的子问题。以解答子问题一次而再使用其解答数次，即可以彻底地得出其所需时间。此一方法称为动态规划。
动态规划算法步骤：
- 首先思考：若只有两个矩阵相乘，则只会有一种方法去乘它们，所有其最小成本为乘积的成本，那么接下来可以按照如下方法计算。
- 取得矩阵的序列且将其分成两个子序列。
- 找出乘完每一子序列的最小成本。
- 将成本加起来，并加上两个结果矩阵相乘的成本。
- 在每一矩阵序列可分开的位置运作，并取其最小值。

总结成状态转移方程即为：

  m[i,j] = 0                             i=j
  m[i,j] = min{m[i,k]+m[k+1,j]+Pi-1PkPj} i<j

m[i,j] 为 A1A2...Aj 的最优完全加括号所需的最少标量乘法次数，对于整个问题来说，计算 A1...n 的最节省方式的代价自然应为 m[1,n]

Pi-1PkPj 是计算 Ai...k 和 Ak+1...j 的积所消耗的时间

伪代码：

  Matrix-Chain-Order(int p[])
  {
      n = p.length - 1;
      for (i = 1; i <= n; i++) 
          m[i,i] = 0;

      for (l=2; l<=n; l++) { // l is chain length
          for (i=1; i<=n-l+1; i++) {
              j = i+l-1;
              m[i,j] = MAXINT;
              for (k=i; k<=j-1; k++) {
                  q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];//Matrix Ai has the dimension  p[i-1] x p[i].
                  if (q < m[i,j]) {
                      m[i,j] = q;
                      s[i,j] = k;
                  }
              }
          }
      }
  }

稍加考察，可以知道运行时间为 Θ(n^3)，辅助空间为 Θ(n^2)

上述过程除了确定最少标量乘法数，还计算了用于构造最优解的表格 s[1..n,1..n] 。每一项s[i,j]记录了AiAi+1...Aj的最佳加括号的在Ak和Ak+1之间分裂的值k，于是我们知道最终矩阵积A1..n的最佳计算是A1..s[1,n] As[1,n]+1..n。

于是可以有打印过程：

  PRINT-OPTIMAL-PARENS(s,i,j)
  if i = j
      then print "A"i
      else print "("
          PRINT-OPTIMAL-PARENS(s,i,s[i,j])
          PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)
          print ")"

本文由永利集团登录网址发布于永利集团登录网址,转载请注明出处：动态规划永利游戏平台

关键词：

动态规划永利游戏平台

算法学习 - 最长公共子序列（LCS）C++实现

动态规划（Dynamic Programming）

最长公共子序列

1、 什么是动态规划，我们要如何描述它？

动态规划

动态规划DP

2、“状态”代表什么及如何找到它？

分析LCS

LCS（longest common subsequence）

3、DP 算法步骤

代码实现分析

4、最长非降子序列（LIS）

代码

另一个解法：利用LCS思想（第9点）

5、最大乘积子串

6、Unique Paths

7、Unique Paths II

8、Minimum Path Sum

9、Triangle

10、最长公共子序列（LCS）

11、编辑距离

12、交替字符串

13、矩阵链乘积

1、什么是动态规划，我们要如何描述它？