动态规划专题

动态规划专题

---

综述：

本篇文章将会讲述各种常见的动态规划模型，将用 闫氏dp分析法 对动态规划的问题进行分析，使得整个过程更加简单明了。

dp问题能够解决的问题：

• 求最大值，最小值， 方案数

读完这篇文章可以解决的问题：

1. 是哪种模型的dp问题
2. 状态表示如何进行表示
3. 状态计算如何分析
4. 如何对dp问题的数组进行初始化

---

第一个模型：数字三角形模型

题目1 链接： 摘花生

闫氏dp分析法主要思想 : 从集合角度思考问题，主要从 状态表示 和 状态计算 两个 方面进行思考

状态表示： f(i, j) : 表示从起点(1, 1), 走到(i, j)所能摘取到的花生数量的最大值

f( i, j ) 这个状态可以由f( i - 1, j ) （当前这个格子的同一列的上一行） 和 f( i, j - 1 ) (当前这个格子的同一行的左边一列)这两个状态转移过来
状态计算： f(i, j) = max( f( i - 1, j ) , f( i, j - 1 ) )

---

时间复杂度 ： O ( n ∗ m ) O(n * m) O(n∗m) 一秒之内可以出解

代码区

#include
#include

using namespace std;

const int N = 110;

int n, m;
int g[N][N];//存储每个单元格中花生的数量
int f[N][N];//状态转移方程

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                cin >> g[i][j];
                
       memset(f, 0, sizeof f);
       for(int i = 1; i <= n; i ++)
       {
           for(int j = 1; j <= m; j ++)
           {
               /* dp数组进行初始化：
               因为第一个单元格无法通过f(i - 1, j) 和 f(i, j - 1) 进行转移过来
               所以要进行初始化。
               */
               if(i == 1 && j == 1) f[i][j] = g[i][j];
               else f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];
           }
       }
       
       cout << f[n][m] << endl;
    }
    
    return 0;
}

可能存在的疑问：

为什么dp数组的下标有时候从1开始， 有时候从0开始？
这和状态转移方程有关：f(i, j) = max( f( i - 1, j ) , f( i, j - 1 ) )，

如果从下标从1开始， 则只有起点(1, 1)需要初始化，因为 f( i - 1, j ) , f( i, j - 1 )，起点为1时，i - 1 = 0，j - 1 = 0, 有缓冲, 因为求的是最大值， 所以f(0, i) 和 f(i, 0)初始化成0就行了。、

如果下标从0开始， 因为 f( i - 1, j ) , f( i, j - 1 )，起点为0时，i - 1 = -1，j - 1 = -1, 数组下标不能是负数。所以要加上许多边界的特判。

总结： 做此类数字三角形模型的dp问题， 数组下标最好从1开始， 省去特判条件

---

题目2 链接： 最低通行费

分析：
因为题目求的是最小费用， 求的是最小值， 考虑使用dp。
注意看这题有一个要求 商人必须在 (2N−1) 个单位时间穿越出去，且只能向上下左右四个方向移动且不能离开网格， 也就是只能穿越 2N - 1 个格子， 每穿越一个格子通行费用都会增加， 按题目要求，我们必须向左边走n步，向下边走 n - 1 步。

状态表示： f(i, j) : 表示从起点(1, 1), 走到(i, j)所缴纳的最小通行费用

f( i, j ) 这个状态可以由f( i - 1, j ) （当前这个格子的同一列的上一行） 和 f( i, j - 1 ) (当前这个格子的同一行的左边一列)这两个状态转移过来
状态计算： f(i, j) = max( f( i - 1, j ) , f( i, j - 1 ) )

dp数组的初始化：

数组下标从1开始， 因为只有起点(1, 1), 无法通过 状态转移方程f(i, j) = max( f( i - 1, j ) , f( i, j - 1 ) )转移方程转移过来， 所以特判起点f(1, 1) = w(1, 1) 即可。
因为要求的是最小值， 所以缓冲地带f(i, 0), f(0, i)初始化成 正无穷(0x3f3f3f3f)即可，0x3f3f3f3f3f详解

时间复杂度： O ( n 2 ) O(n ^ 2) O(n2) 一秒之内可以出解

代码区

#include
#include

using namespace std;

const int N = 110;

int n;
int w[N][N];//存储每个格子通行所需的费用
int f[N][N];//集合

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> w[i][j];
            
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(i == 1 && j == 1) f[i][j] = w[i][j];
            else
            {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
            }
        }
    }
    
    cout << f[n][n] << endl;
    
    return 0; 
    
}

---

题目3 链接： 方格取数

分析：

至于这题的方案究竟是如何进行选取的， 讲解