动态规划（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
| 1 2 |
|
Sample Output
| 1 |
|
思路：此题的切入点就是动态规划，通过动归来确定哪些字符是最长公共子序列中的字符，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;
}简单案例
0-1背包问题。在这个问题中，给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。每种物品只有一个，可以选择放或不放。
#include <stdio.h>
#include <stdlib.h>
#define MAX_WEIGHT 100
#define NUM_ITEMS 5
// 定义物品结构体
typedef struct {
int weight;
int value;
} Item;
// 初始化物品数组
Item items[NUM_ITEMS] = {
{10, 60},
{20, 100},
{30, 120},
{40, 130},
{50, 150}
};
// 动态规划求解0-1背包问题
int knapsack(int W, Item items[], int n) {
int i, w;
int K[NUM_ITEMS+1][MAX_WEIGHT+1];
// 初始化K[][]表
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (items[i-1].weight <= w)
K[i][w] = (items[i-1].value + K[i-1][w-items[i-1].weight] > K[i-1][w]) ?
(items[i-1].value + K[i-1][w-items[i-1].weight]) : K[i-1][w];
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
int main() {
int max_weight = 50; // 背包的最大重量
int max_value = knapsack(max_weight, items, NUM_ITEMS); // 计算最大价值
printf("The maximum value is %d\n", max_value);
return 0;
}在这个程序中，我们定义了一个Item结构体来表示物品的重量和价值。knapsack函数通过动态规划求解0-1背包问题，它使用一个二维数组K[][]来存储子问题的解。最后，main函数调用knapsack函数并打印出最大价值。
请注意，这个案例是为了展示动态规划的基本思想，实际应用中可能需要考虑更多的边界条件和优化。
