动态规划小结 - 二维动态规划 - 时间复杂度 O(n*n)的棋盘型,题 [LeetCode] Minimum Path Sum,Unique Paths II,Edit Distance
引言
二维动态规划中最常见的是棋盘型二维动态规划。
即
func(i, j) 往往只和 func(i-1, j-1), func(i-1, j) 以及 func(i, j-1) 有关
这种情况下,时间复杂度 O(n*n),空间复杂度往往可以优化为O(n)
例题 1
Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
时间复杂度 O(n*n),空间复杂度O(n)的解法。
这里用了个以前不用的技巧,当想把数组初始化为非0的值时,不用memset,而改用vector表示数组。
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
if(grid.size() == || grid[].size() == ) return ;
int H = grid.size(), W = grid[].size();
vector<int> path(W+, INT_MAX);
path[] = ;
for(int i = ; i <= H; ++i)
for(int j = ; j <= W; path[j] = min(path[j-], path[j]) + grid[i-][j-], ++j);
return path[W];
}
};
例题 2
Unique Paths II
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Above is a 3 x 7 grid. How many possible unique paths are there?
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1
and 0
respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2
.
Note: m and n will be at most 100.
时间复杂度 O(n*n),空间复杂度O(n)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
if(obstacleGrid.size() == || obstacleGrid[].size() == ) return ;
int H = obstacleGrid.size(), W = obstacleGrid[].size();
int paths[W+]; memset(paths, , sizeof(paths));
paths[] = (obstacleGrid[][] ? : );
for(int i = ; i <= H; ++i){
for(int j = ; j <= W; ++j){
paths[j] = (obstacleGrid[i-][j-] ? : paths[j-] + paths[j]);
}
}
return paths[W];
}
};
例题 3
很熟悉的 Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
类似的还有http://basicalgos.blogspot.com/上的 53. Edit Distance between strings
这道题目我们要设置两个变量,i和j, E(i, j) 表示word1中以i 结尾的子串到表示word2中以j 结尾的子串的距离。
状态转移方程借助53. Edit Distance between strings上的这张图片来说明:
LeetCode那道题的实现代码,时间复杂度 O(n*n),空间复杂度O(n)
class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.empty() && word2.empty()) return ;
int len1 = word1.length(), len2 = word2.length();
int A[len2+]; int pre;
memset(A, , sizeof(A));
for(int i = ; i <= len1; ++i){
for(int j = ; j <= len2; ++j){
int Min = INT_MAX;
if(i > ) Min = min(A[j]+, Min);
if(j > ) Min = min(A[j-]+, Min);
if(i > && j > ) Min = min(Min, pre+(word1[i-] == word2[j-] ? : ));
if(i == && j == ) Min = ;
pre = A[j];
A[j] = Min;
}
}
return A[len2];
}
};
后记
棋盘型二维动态规划典型的题目还有“寻找最长公共子串(substring)”,“寻找最长公共子序列(subsequence)”。
这些都可以给出时间复杂度 O(n*n),空间复杂度O(n)的解。
最新文章
- JAVA环境变量和TomCat服务器配置
- 在SQL2008配置数据库镜像1418错误的处理
- 非常详细GC学习笔记
- Spring4.0+Hibernate4.0+Struts2.3整合包括增删改查案例,解决整合中出现的异常
- 一步步学Mybatis-怎么样实现动态SQL查询(6)
- hdu-5701 中位数计数(中位数)
- [iOS微博项目 - 1.5] - NavigationBar标题按钮
- [Linked List]Reorder List
- java11 - GUI图形用户界面编程
- Hibernate Validator 6.0.9.Final - JSR 380 Reference Implementation: Reference Guide
- BeanUtils工具类
- NYOJ_1274_信道安全 -
- openFileDialog的使用
- 洛谷 P1880 [NOI1995] 石子合并(区间DP)
- cocos2d-x JS 四人麻将中的服务器位置与客户端位置转换相关
- SpringBoot热部署:spring-boot-devtools在Idea中热部署方法
- WCF错误:413 Request Entity Too Large 的一个解决方法
- poj2528(线段树+区间离散)
- Elasticsearch 基础理论 &; 配置调优
- linux进程、调度、线程、进程上下文等几点理解