动态规划概念和实例讲解

动态规划（Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

严格意义上，动态规划只能用来解决最优化问题，但在OI中，计数等非最优化问题的递推解法也常被不规范地称作 DP。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。

一、简介

动态规划算法是五种常见的算法之一，通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

动态规划主要用于求解以时间划分阶段的动态过程的优化问题，动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。它往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

二、适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。，适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理，即最优子结构性质，最优化原理可这样阐述:一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

无后效性，将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

三、动态规划算法的设计

动态规划算法的设计主要有两种方法：

（1）自顶向下（又称记忆化搜索、备忘录）：基本上对应着递归函数实现，从大范围开始计算，要注意不断保存中间结果，避免重复计算

（2）自底向上（递推）：从小范围递推计算到大范围

四、经典例题

动态规划在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。

例题一：最长公共子序列问题（求LCS具体是什么）

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：abcicba 和 abdkscab，则 ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

第1行：字符串A 

第2行：字符串B 

(A,B的长度 <= 1000)

Output

输出最长的子序列，如果有多个，随意输出1个。

Sample Input

abcicba
abdkscab

Sample Output

abca

思路：此题的切入点就是动态规划，通过动归来确定哪些字符是最长公共子序列中的字符，mat[i][j] 表示第一个序列的前i个字符和第二个序列的前j个字符的公共子序列，动态转移方程为：

 dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1] + (A[i]==B[j] ? 1 : 0))，表示在这三种状态中取到最大值，

（1）第一种状态表示不录入第一个序列的第i个字符时的最长公共子序列，

（2）第二种状态表示不录入第二个序列的第j个字符时的最长公共子序列，

（3）第三种状态表示第一个序列的前i-1个字符与第二个序列前j-1个字符的公共子序列加上最后一个字符的录入状态，如果最后的一个字符相等则录入状态为1，否则为0。

然后根据动归的状态，来判断我们要求得的序列中的字符有哪些。

代码如下：

#include<queue>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
 
using namespace std;
 
char a[1001], b[1001];
int dp[1001][1001], len1, len2;
 
void lcs(int i, int j)
{
    for(i=1; i<=len1; i++)
    {
        for(j=1; j<=len2; j++)
        {
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else if(dp[i-1][j] > dp[i][j-1])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = dp[i][j-1];
        }
    }
}
 
void llcs()
{
    int i, j, z = 0;
    char c[1001];
    memset(c, 0, sizeof(c));
    i = len1, j = len2;
    while(i!=0 && j!=0)
    {
        if(a[i-1] == b[j-1])
        {
            c[z++] = a[--i];
            j--;
        }
        else if(dp[i-1][j] < dp[i][j-1])
            j--;
        else if(dp[i][j-1] <= dp[i-1][j])
            i--;
    }
    for(i=z-1; i>=0; i--)
        printf("%c", c[i]);
    printf("\n");
 
}
 
int main()
{
    while(~scanf(" %s", a))
    {
        scanf(" %s", b);
        memset(dp, 0, sizeof(dp));
        len1 = strlen(a);
        len2 = strlen(b);
        lcs(len1, len2);
        llcs();
    }
    return 0;
}

例题二：爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

          （1） 阶 + 1 阶

          （2）阶

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

          （3）1 阶 + 1 阶 + 1 阶

          （4）1 阶 + 2 阶

          （5）2 阶 + 1 阶

思路：

爬楼梯算是DP的经典题目，递归+记忆化，也就是递推，我们需要定义好状态，还有状态的转移方程。最后爬的步数还是得看之前的，即依赖之前的步骤。

1. 反着考虑，有几种方案到第i阶楼梯，答案是2种：

第i-1阶楼梯经过一步

第i-2阶楼梯经过两步

假设count(i)表示到第i阶楼梯方案的个数，则count(i) = count(i-1) + count(i-2)

第一阶是1种，第二阶是2种。代码如下：

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = [1,2]   #一次就只能走这两步
        for i in range(2,n):
            count.append(count[i-1]+count[i-2])	#不停地把后面的台阶的结束放到count里面
        return count[n-1]

这里是O(n!)

2. 我们想到可以转化为fibonaqi问题。假设一共有10阶楼梯，每步可以爬1步或者2步，那么你爬到10阶一共有两种方法，从8阶爬2步，或从9阶爬1步，那么爬到9阶也是这样，那这就是一共基本的斐波那契数列。

dp[i] = dp[i-1] + dp[i-2]

i-1的时候跳一步可以到达i

i-2的时候跳一步是i-1，这个变成dp[i-1]的子问题了,直接跳两步可以到达i

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1 for i in range(n+1)]   #状态的定义
        for i in range(2,n+1):
            dp[i] = dp[i-1]+dp[i-2]	#状态转移方程
        return dp[n]

这里应该是O(n)

3. 还有一种更快速的，列表初始化好，然后再用fibonaqi数列转移方程。

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        condition = [0]*(n+1)		#牛逼的初始化列表
        condition[0] = 1
        condition[1] = 1
        for i in range(2,n+1):
            condition[i] = condition[i-1]+condition[i-2]   #依然还是状态转移fibonaqo
        return condition[n]

这里列表初始化只用来O(1)，最后复杂度为O(n)。