算法-动态规划(二)

发表于 分类于 ，
本文字数： 3.2k 阅读时长 ≈ 3 分钟

概述

本文主要介绍线性 DP 中的数字三角形模型，与该模型相关的题目有：数字三角形、摘花生、最低通行费、方格取数。

数字三角形

题目描述及示例

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
// 第一行包含整数n，表示数字三角形的层数。
5
// 接下来n行，每行包含若干整数，其中第i行表示数字三角形第i层包含的整数。
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
    
Output:
// 输出一个整数，表示最大的路径数字和。
30

解题思路

  • 数据存储

    triangle[i][j] 用于存储数字三角形 (存储方式与输入示例相同，每行数据从前往后依次存储即可)。

  • 状态表示

    既然数据是二维的，状态表示大概率也是二维的。我们可以这样定义 $f[i][j]$：以 $triangle[0][0]$ 为起点、$triangle[i][j]$ 为终点的所有路径中最大的路径数字和。

  • 状态转移

    “在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点” 表明：对于 $f[i][j]$ 而言，它可由其左上方结点所示状态或右上方结点所示状态转移得到。故而状态转移方程可表示如下：

    $$f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]$$

    如果 $f[i][j]$ 为最左侧结点所示状态，则它只能由其右上方结点所示状态转移得到；如果 $f[i][j]$ 为最右侧结点所示状态，则它只能由其左上方结点所示状态转移得到。

  • 状态初始化

    对于此题目而言，状态初始化比较简单，直接指定 $f[0][0] = triangle[0][0]$ 即可。

摘花生

题目描述及示例

Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地 (如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty 只能向东或向南走，不能向西或向北走。问 Hello Kitty 最多能够摘到多少颗花生？

1
2
3
4
5
6
7
8
9
10
Input:
// 第一行包含两个整数，分别代表花生苗的行数R和列数C。
2 3
// 接下来R行数据，从北向南依次描述每行花生苗的情况。
2 3 4
1 6 5
    
Output:
// 输出一个整数，表示Hello Kitty能摘到得最多的花生颗数。
16

解题思路

  • 数据存储

    rectangle[i][j] 用于存储花生苗信息。

  • 状态表示

    与上题类似，我们可以这样定义状态 $f[i][j]$：以 $rectangle[0][0]$ 为起点、$rectangle[i][j]$ 为终点的所有路径中，Hello Kitty 所能摘到的最大花生数。

  • 状态转移

    “Hello Kitty 只能向东或向南走” 表明：对于 $f[i][j]$ 而言，它可由其左侧状态或其上侧状态转移得到。故而状态转移方程可表示如下：

    $$f[i][j] = max(f[i][j - 1], f[i - 1][j]) + rectangle[i][j]$$

    如果 $f[i][j]$ 为最左侧状态，则它只能由其上侧状态转移得到；如果 $f[i][j]$ 为最上侧状态，则它只能由其右侧状态转移得到。

  • 状态初始化

    对于此题目而言，状态初始化也是比较简单，直接指定 $f[0][0] = rectangle[0][0]$ 即可。

最低通行费

题目描述及示例

一个商人穿过一个 $N\times N$ 的正方形网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。
每穿越中间 1 个小方格，都要花费 1 个单位时间。商人必须在 (2N-1) 个单位时间内穿越出去，而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
// 第一行是一个整数，表示正方形的宽度N。
5
// 接下来N行，为网格上每个小方格的费用。
1  4  6  8  10 
2  5  7  15 17 
6  8  9  18 20 
10 11 12 19 21 
20 23 25 29 33
    
Output:
// 输出一个整数，表示至少需要的费用。
109

解题思路

  • 数据存储

    rectangle[i][j] 用于存储网格费用。

  • 状态表示

    这道题目意思比较隐晦，我们先对题意作一简单分析：“商人必须在 (2N-1) 个单位时间内穿越出去” ，这句话也就是说：商人只能向下或向右行走，而不能走回头路。

    此时题意与上题基本类似，我们可以这样定义状态 $f[i][j]$：从 $rectangle[0][0]$ 出发、到达 $rectangle[i][j]$ 所需的最少费用。

  • 状态转移

    根据 “商人必须在 (2N-1) 个单位时间内穿越出去” ，状态转移方程可表示如下：

    $$f[i][j] = min(f[i][j - 1],f[i - 1][j]) + rectangle[i][j]$$

    如果 $f[i][j]$ 为最左侧状态，则它只能由其上侧状态转移得到；如果 $f[i][j]$ 为最上侧状态，则它只能由其右侧状态转移得到。

  • 状态初始化

    对于此题目而言，状态初始化也是比较简单，直接指定 $f[0][0] = rectangle[0][0]$ 即可。

方格取数

题目描述及示例

设有 $N \times N$ 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字 0。如下图所示：

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数 (取走后的方格中将变为数字0)。此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input:
// 第一行为一个整数，表示方格图的宽度。
8
// 接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数,一行“0 0 0”表示结束。
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
    
Output:
// 输出一个整数，表示两条路径上取得的最大和。
67

解题思路

  • 数据存储

    rectangle[i][j] 用于存储方格信息。

  • 状态表示

    这道题可以先执行 DP 求取一个最大和，随后将相关方格中的数置为 0，再次执行 DP 取得一个最大和，二者相加即是结果。

    这道题目可以看做是数字三角形模型在二维空间中的扩展，所以我们直接在此空间之上构建状态。我们可以这样定义状态 $f[i1][j1][i2][j2]$：以 $rectangle[0][0]$ 为起点、 $rectangle[i1][j1]$ 和 $rectangle[i2][j2]$ 分别为终点的所有路径中，所能取得数字的最大和。

  • 状态转移

    由于涉及两个终点，类比数字三角形模型可知：当前状态 $f[i1][j1][i2][j2]$ 可由四个状态转移得到。具体的状态转移方程表示如下：

    $$f[i1][j1][i2][j2] = max(f[i1][j1 - 1][i2][j2 - 1],f[i1 - 1][j1][i2 - 1][j2],f[i1][j1 - 1][i2 - 1][j2],f[i1 - 1][j1][i2][j2 - 1]) + rectangle[i1][j1] + rectangle[i2][j2] (i1 \neq i2 \ 或 \ j1 \neq j2)$$

    $$f[i1][j1][i2][j2] = max(f[i1][j1 - 1][i2][j2 - 1],f[i1 - 1][j1][i2 - 1][j2],f[i1][j1 - 1][i2 - 1][j2],f[i1 - 1][j1][i2][j2 - 1]) + rectangle[i1][j1] (i1 = i2 \ 且 \ j1 = j2)$$

  • 状态初始化

    状态初始化仍然是比较简单的，直接指定 $f[0][0][0][0] = rectangle[0][0]$ 即可。

相关文章