文章目录
- 第一题：二维矩阵中的最短路径
- 题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例
- 输出样例
- 解题思路&C++题解
-
- 第二题：01 串的满足条件的个数
- 题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例
- 输出样例
- 解题思路&C++题解
-
第一题：二维矩阵中的最短路径
题目描述
给定一个二维矩阵，包含 n 行 m 列，每个元素都是整数。现在要求从左上角 (1,1) 出发，每次只能向右或向下移动，最后到达右下角 (n,m)。在每一步中，你可以选择使用一次费用为 ci 的道具，使得你可以直接跳到 (i+1,m) 这一列。问最少花费多少的费用，才能从左上角 (1,1) 到达右下角 (n,m)。
输入格式
第一行包含两个整数 n,m。
接下来 n 行，每行包含 m 个整数，表示矩阵的元素。
接下来一行包含 m 个整数 c1,c2,…,cm，表示每列的费用。
输出格式
输出一个整数，表示最少的花费。
数据范围
1≤n,m≤1000,
0≤矩阵元素≤1000,
0≤ci≤1000
输入样例
4 4
1 3 5 9
2 3 4 5
4 5 6 7
8 9 1 2
1 2 3 4
输出样例
5
解题思路&C++题解
算法
(动态规划)
O
(
n
2
)
O(n^2)
O(n2)
状态表示：
d
p
i
,
j
dp_{i,j}
dpi,j 表示到达
(
i
,
j
)
(i,j)
(i,j) 这个位置所需要的最小花费。
状态转移方程
d
p
i
,
j
=
m
i
n
(
d
p
i
,
j
−
1
+
c
o
s
t
j
,
d
p
i
−
1
,
j
+
c
o
s
t
j
)
dp_{i,j} = min(dp_{i,j-1} + cost_{j}, dp_{i-1,j} + cost_{j})
dpi,j=min(dpi,j−1+costj,dpi−1,j+costj)
表示从
(
i
−
1
,
j
)
(i-1,j)
(i−1,j) 或者
(
i
,
j
−
1
)
(i,j-1)
(i,j−1) 转移到
(
i
,
j
)
(i,j)
(i,j) 所需的最小费用。
因为只能向右或向下移动，所以转移时只能从
(
i
−
1
,
j
)
(i-1,j)
(i−1,j) 或者
(
i
,
j
−
1
)
(i,j-1)
(i,j−1) 这两个位置转移过来。
初始化：
d
p
1
,
j
=
c
o
s
t
1
+
d
p
1
,
j
−
1
dp_{1,j} = cost_{1} + dp_{1,j-1}
dp1,j=cost1+dp1,j−1，
d
p
i
,
1
=
c
o
s
t
1
+
d
p
i
−
1
,
1
dp_{i,1} = cost_{1} + dp_{i-1,1}
dpi,1=cost1+dpi−1,1
最终结果：
d
p
n
,
m
dp_{n,m}
dpn,m
下面是 c++ 代码实现：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int a[N][N];
int cost[N];
int dp[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> a[i][j];
for (int i = 1; i <= m; i ++ )
cin >> cost[i];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
dp[i][j] = min(dp[i][j - 1] + cost[j], dp[i - 1][j] + cost[j]);
cout << dp[n][m] << endl;
return 0;
}
上面的代码实现了状态转移方程的过程。
注意：
第二题：01 串的满足条件的个数
题目描述
给定一个整数 n，请你求出有多少个长度为 n 的 01 串，满足下列条件：
在二进制表示下，每一位都是 0 或者 1。
每个 0 后面必须跟着至少一个 1。
每个 1 后面可以跟着任意个数的 0。
输入格式
第一行包含一个整数 n，表示 01 串的长度。
输出格式
输出一个整数，表示满足条件的 01 串的个数。
数据范围
1≤n≤17
输入样例
4
输出样例
5
解题思路&C++题解
算法
(动态规划)
O
(
n
2
)
O(n^2)
O(n2)
状态表示：
d
p
i
,
j
dp_{i,j}
dpi,j 表示前 i 位中有 j 个 1 的情况下，满足条件的 01 串的个数。
状态转移方程
d
p
i
,
j
=
d
p
i
−
1
,
j
−
1
dp_{i,j} = dp_{i-1,j-1}
dpi,j=dpi−1,j−1，表示在第 i 位放 1。
d
p
i
,
j
=
d
p
i
−
1
,
j
dp_{i,j} = dp_{i-1,j}
dpi,j=dpi−1,j，表示在第 i 位放 0。
初始化：
d
p
1
,
1
=
1
dp_{1,1} = 1
dp1,1=1，
d
p
1
,
0
=
0
dp_{1,0} = 0
dp1,0=0
最终结果：
d
p
n
,
j
dp_{n,j}
dpn,j，其中
0
≤
j
≤
n
0 \le j \le n
0≤j≤n
下面是 c++ 代码实现：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int n;
int dp[N][N];
int main()
{
cin >> n;
dp[1][1] = 1;
for (int i = 2; i <= n; i ++ )
for (int j = 0; j <= i; j ++ )
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
int res = 0;
for (int i = 0; i <= n; i ++ )
res += dp[n][i];
cout << res << endl;
return 0;
}
上面的代码实现了状态转移方程的过程。
注意：
-
由于在第 i 位可以放 0 或者 1，所以 j 的范围是
0
≤
j
≤
i
0 \le j \le i
0≤j≤i。
-
在求最终结果的时候，需要将所有的
d
p
n
,
j
dp_{n,j}
dpn,j 累加起来。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
