动态规划

发表于 更新于 分类于 ， 阅读次数： 本文字数： 391 阅读时长 ≈ 1 分钟

两个性质

  1. 最优子结构：问题的最优解由其子问题的最优解组合而成；且子问题可独立求解；
  2. 重叠子问题：子问题的算法相同。

步骤

  1. 问题结构分析（数学语言描述）；

  2. 递推关系建立；

  3. 自底向上计算，确立计算顺序；

  4. 最优方案追踪（记录数组回溯）

复杂度

复杂度取决于子问题的个数和子问题的复杂度。

类型

背包DP

背包问题-knapsack problem

线性DP

最长上升子序列 - LIS

递推关系：$F[i] =\max_{0 \le j < i, v[j] < v[i]}(F[j] + i)$

边界：$F[0] = 0$

最长公共子串 - LCS

递推关系：$F[i, j]=\max \left{\begin{array}{l}
F[i-1, j] \\
F[i, j-1] \\
F[i-1, j-1]+1 \quad \text { if } A[i]=B[j]
\end{array}\right.$

边界：$F[0,] = F[,0] = 0$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

#define N 100
#define max(a,b) (a)>(b)?(a):(b)

int dp[N][N]={0};//dp value

int main() {
    char t[N]="abcdefg",s[N]="abcdgaaabcdef";//input
    
    for(int i=0;i<strlen(s);i++)
        for(int j=0;j<strlen(t);j++)
          if(s[i]==t[j])dp[i+1][j+1]=dp[i][j]+1;//decrease-and-conquer
          else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);//divide-and-conquer

    cout<<dp[strlen(s)][strlen(t)];//output
}

数组DP

区间DP

最小编辑距离

钢铁切割

矩阵链乘法

例题

LCS例题题解

区别

  • 与 分治：分治是独立的子问题
  • 与 贪心：贪心自顶向下

Reference

[1].Dynamic Programming —— Geeksforgeeks

[2].Introduction to algorithms

[3].算法设计与分析 - 北航童咏昕教授