动态规划 - 路径专题
2018-05-23 本文已影响0人
tingjieee_19e5
1.求最短路径和
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.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == 0)
return 0;
int cols = grid.size();
int rows = grid[0].size();
vector<vector<int>> dp(cols,vector<int>(rows,0));
dp[0][0] = grid[0][0];
for(int i = 1; i < cols;++i) {
dp[i][0] = grid[i][0] + dp[i-1][0];
}
for(int i = 1; i < rows;++i) {
dp[0][i] = grid[0][i] + dp[0][i-1];
}
for(int i =1; i< cols;++i){
for(int j =1;j < rows;++j){
dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1]);
}
}
return dp[cols-1][rows-1];
}
};
- 求不同路径
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).
How many possible unique paths are there?
Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> record(n,vector<int>(m, 0));
for(int i =0;i < n;++i){
record[i][0] = 1;
}
for(int i =0;i < m;++i){
record[0][i] = 1;
}
for(int i = 1;i < n;++i){
for(int j =1; j < m;++j){
record[i][j] = record[i-1][j] + record[i][j-1];
}
}
return record[n-1][m-1];
}
};
- 求不同路径
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).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
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.
Note: m and n will be at most 100.
Example:
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if(obstacleGrid.size() == 0)
return 0;
//int *pRecordPath = new int[obstacleGrid.size()*obstacleGrid[0].size()]();
//for(int i = 0; i < obstacleGrid.size()*obstacleGrid[0].size();++i) pRecordPath[i] = -1;
int cols = obstacleGrid.size();
int rows = obstacleGrid[0].size();
vector<vector<int>> record(cols,vector<int>(rows, 0));
for(int i =0;i < cols;++i){
if(obstacleGrid[i][0] == 0)
record[i][0] = 1;
else
break;
}
for(int i =0;i < rows;++i){
if(obstacleGrid[0][i] == 0)
record[0][i] = 1;
else
break;
}
for(int i =1;i < cols;++i){
for(int j = 1; j < rows;++j){
if(obstacleGrid[i][j] == 0)
record[i][j] = record[i-1][j] + record[i][j-1];
else
record[i][j] = 0;
}
}
return record[cols-1][rows-1];
//return uniquePath(obstacleGrid,0,0,record);
}
int uniquePath(const vector<vector<int>>& grid,int col,int row,vector<vector<int>> &pRecord) {
int cnt = 0;
if(col == grid.size()-1 && row == grid[0].size()-1 && grid[col][row] == 0)
return 1;
else if(col < grid.size() && row < grid[0].size() && grid[col][row] == 0) {
cnt += uniquePath(grid,col+1,row,pRecord);
cnt += uniquePath(grid,col,row+1,pRecord);
return cnt;
}
return 0;
}
};
- 最大子序列和，最大子序列乘积
- 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
//brust force
bool wordBreak(string s,vector<string>& Dict,int start){
if(start == s.length())
return true;
for(string a : Dict){
int len = a.length();
int end = len + start;
if(end > s.length()) continue;//return false;
if(s.substr(start,len) == a) {
if(wordBreak(s,Dict,start+len))
return true;
}
}
return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
if(s.size() == 0 && wordDict.size() == 0)
return true;
//std::unordered_set<string> Dict;
set<string> Dict;
for(int i = 0; i < wordDict.size();++i){
Dict.insert(wordDict[i]);
}
return wordBreak(s,wordDict,0);
/*vector<int> Check(s.size()+1,0);
Check[0] = 1;
for(int i = 1;i <= s.size();++i){
for(int j = 0; j < i;++j){
if(Check[j]==1 && Dict.find(s.substr(j,i-j)) != Dict.end() ){
Check[i] = 1;
break;
}
}
}
return Check[s.size()]== 1;// ? true : false;
*/
}
//Dynamic programming
/*
这道题仍然是动态规划的题目，我们总结一下动态规划题目的基本思路。
首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。
然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。
最后我们需要考虑的就是起始条件的值。
接下来我们套用上面的思路来解这道题。
首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔数组来存储信息。
然后假设我们现在拥有res[0,...,i-1]的结果，我们来获得res[i]的表达式。
*/
bool wordBreak(string s, vector<string>& wordDict) {
if(s.size() == 0 && wordDict.size() == 0)
return true;
std::unordered_set<string> Dict;
for(int i = 0; i < wordDict.size();++i){
Dict.insert(wordDict[i]);
}
vector<int> Check(s.size()+1,0);
Check[0] = 1;
for(int i = 1;i <= s.size();++i){
for(int j = 0; j < i;++j){
if(Check[j]==1 && Dict.find(s.substr(j,i-j)) != Dict.end() ){
Check[i] = 1;
break;
}
}
}
return Check[s.size()]== 1;// ? true : false;
}
