同学们可能对什么使用正序求解，什么时候倒序求解有一点疑问。
我们现在说的是一种bottom-up的方式，每个大问题用子问题去求解，保证每次要用到的子问题都已经先被计算过了，我们也把它叫做递推(recurrence)。
还有一种叫做记忆化搜索（memorization），就是递归得求答案，并把算过的内容存在数组里，因为它是从上往下算的，这是一种top-down的方式。
一般来说动态规划题两种都可以用，但是，有些时候某一种写法能比另一种写法简单很多，所以两种写法都要掌握
107. Word Break
DP需要建立对应表，将它一一填入
unordered_set找是否在 dict中
class Solution {public:/** @param s: A string* @param dict: A dictionary of words dict* @return: A boolean*/bool wordBreak(string &s, unordered_set<string> &dict) {// write your code hereint m = s.size();vector<bool> result(m + 1, false);result[0] = true;for (int i = 0; i < s.size(); i ++){for (int j = i; j < s.size(); j ++){if (result[i] != true){continue;}// cout << s.substr(i, j - i + 1);if (dict.count(s.substr(i, j - i + 1))){result[j + 1] = true;}}}return result[m];}};
109 Triangle
class Solution {public:/*** @param triangle: a list of lists of integers* @return: An integer, minimum path sum*/int minimumTotal(vector<vector<int>> &triangle) {// write your code hereint size = triangle.size();vector<vector<int>> res(size, vector<int>(size));res[0][0] = triangle[0][0];for(int i = 1; i < size; i++){res[i][0] = res[i - 1][0] + triangle[i][0];res[i][i] = res[i - 1][i - 1] + triangle[i][i];}for(int i = 2; i < size; i++){for (int j = 1; j < i ; j++){res[i][j] = min(res[i - 1][j] , res[i - 1][j - 1]) + triangle[i][j];}}int min = INT_MAX;for (int i = 0; i < size; i++){if (res[size - 1][i] < min){min = res[size - 1][i];}}return min;}};
683. Word Break III
class Solution {
public:
/*
* @param : A string
* @param : A set of word
* @return: the number of possible sentences.
*/
int wordBreak3(string& s, unordered_set<string>& dict) {
// Write your code here
vector<int> res(s.size() + 1);
transform(s.begin(), s.end(), s.begin(), ::tolower);
unordered_set<string> hs;
for(string x : dict) {
transform(x.begin(), x.end(), x.begin(), ::tolower);
hs.insert(x);
}
dict = hs;
for (int i = 1; i < s.size() + 1; i++){
if (dict.find(s.substr(0, i)) != dict.end()){
res[i] = 1;
}
for (int j = 0; j < i; j++){
if(dict.find(s.substr(j, i - j)) != dict.end()){
res[i] += res[j];
}
}
}
return res[s.size()];
}
};
word break 2
记忆化搜索
class Solution {
public:
/*
* @param s: A string
* @param wordDict: A set of words.
* @return: All possible sentences.
*/
vector<string> wordBreak(string &s, unordered_set<string> &wordDict) {
// write your code here
vector<string> results;
string subsets;
helper(s, 0, wordDict, results, subsets);
return results;
}
void helper(string & s, int index, unordered_set<string> & wordDict, vector<string> & results, string & subsets){
if (index == s.size()){
results.push_back(subsets);
return;
}
if (index > s.size()){
return;
}
if (index > 0){
subsets += " ";
}
for (int i = index; i < s.size(); i ++){
if (wordDict.count(s.substr(index, i - index + 1))){
int temp = subsets.size();
subsets += s.substr(index, i - index + 1);
helper(s, i + 1, wordDict, results, subsets);
if (index == 0){
subsets = subsets.substr(0, 0);
}else{
subsets = subsets.substr(0, temp);
}
}
}
if (index > 0){
subsets.pop_back();
}
}
};
DP
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Map<String,List<String>> record = new HashMap<>();
return subwordBreak(s,wordDict,record);
}
public List<String> subwordBreak(String s, List<String> wordDict, Map <String,List<String>> record){
if(record.containsKey(s)){
return record.get(s);
}
List<String> answer = new ArrayList<>();
if(s.length()==0){
return answer;
}
for(int i=1;i<=s.length();i++){
String p = s.substring(0,i);
if(wordDict.contains(p)){
if(s.length()==i){
answer.add(p);
}else{
List<String> sub = new ArrayList<>();
if(record.containsKey(s.substring(i,s.length()))){
sub = record.get(s.substring(i,s.length()));
}else{
sub =subwordBreak(s.substring(i,s.length()),wordDict,record);
record.put(s.substring(i,s.length()),sub);
}
if(sub.size()>0){
for(String m : sub){
answer.add(p+" "+m);
}
}
}
}
}
return answer;
}
}
wildcard matching
DP
class Solution {
public:
/**
* @param s: A string
* @param p: A string includes "?" and "*"
* @return: is Match?
*/
bool isMatch(string &s, string &p) {
// write your code here
int m = s.size();
int n = p.size();
vector<vector<bool>> DP (m + 1, vector<bool> (n + 1, false));
DP[0][0] = true;
for(int i = 1; i <= m; i ++){
DP[i][0] = false;
}
for (int i = 1; i <= n; i ++){
DP[0][i] = DP[0][i - 1] && (p[i - 1] == '*');
}
for (int j = 1; j <= m; j ++){
for (int i = 1; i <= n; i ++){
if (p[i - 1] == '*'){
DP[j][i] = DP[j][i - 1]|| DP[j - 1][i];
}else if(p[i - 1] == '?'){
DP[j][i] = DP[j - 1][i - 1];
}else{
DP[j][i] = DP[j - 1][i - 1] && (s[j - 1] == p[i - 1]);
}
cout << j << ' ' << i << ' ' << DP[j][i] << endl;
}
}
return DP[m][n];
}
};
记忆化搜索
class Solution {
public:
/**
* @param s: A string
* @param p: A string includes "?" and "*"
* @return: is Match?
*/
bool isMatch(string &s, string &p) {
// write your code here
unordered_map<pair<int, int>, bool, pair_hash> resVec;
return (matchHelper(s, 0, p, 0, resVec));
}
struct pair_hash
{
template<class T1, class T2>
std::size_t operator() (const std::pair<T1, T2>& p) const
{
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
return h1 ^ h2;
}
};
bool matchHelper(string &s, int s_len, string &p, int p_len, unordered_map<pair<int, int>, bool, pair_hash> &resVec) {
pair<int, int> combination = make_pair(s_len, p_len);
if (resVec.find(combination) != resVec.end()) {
return resVec[combination];
}
if (s_len == s.size() && p_len == p.size()) {
resVec[combination] = true;
return true;
}
if (s_len > s.size() || p_len >= p.size()) {
resVec[combination] = false;
return false;
}
bool matched;
if (p[p_len] != '*') {
if (matchChar(s[s_len], p[p_len])) {
matched = matchHelper(s, s_len + 1, p, p_len + 1, resVec);
}
}
else{
matched = (matchHelper(s, s_len, p, p_len + 1, resVec) || matchHelper(s, s_len + 1, p, p_len, resVec));
}
resVec[combination] = matched;
return matched;
}
bool matchChar(char &a, char &b) {
if (a == b or b == '?') {
return true;
}
return false;
}
};
154 Regular Expression Matching
DFS
class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty()) return s.empty();
if (p.size() == 1) {
return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
}
if (p[1] != '*') {
if (s.empty()) return false;
return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}
while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
if (isMatch(s, p.substr(2))) return true;
s = s.substr(1);
}
return isMatch(s, p.substr(2));
}
};
DP
class Solution {
public:
/**
* @param s: A string
* @param p: A string includes "." and "*"
* @return: A boolean
*/
bool isMatch(string &s, string &p) {
// write your code here
int m = p.size();
int n = s.size();
vector<vector<bool>> DP (m + 1, vector<bool> (n + 1, false));
DP[0][0] = true;
for (int i = 1; i <= n; i ++){
DP[0][i] = false;
}
for (int i = 1; i <= m; i ++){
if (p[i - 1] == '*'){
continue;
}else if (i < m && p[i] == '*'){
DP[i][0] = DP[i - 1][0];
DP[i + 1][0] = DP[i - 1][0];
}else{
DP[i][0] = false;
}
// cout << i << '0' << DP[i][0];
}
for (int i = 1; i <= m; i ++){
for (int j = 1; j <= n; j ++){
if (p[i - 1] == '*'){
continue;
}else if (i < m && p[i] == '*' && p[i - 1] == '.'){
DP[i][j] = DP[i][j - 1]|| DP[i - 1][j];
DP[i + 1][j] = DP[i][j - 1]|| DP[i - 1][j];
}else if (i < m && p[i] == '*' && isalpha(p[i - 1])){
if (p[i - 1] == s[j - 1]){
DP[i][j] = DP[i][j - 1] || DP[i - 1][j];
DP[i + 1][j] = DP[i][j - 1]|| DP[i - 1][j];
}else{
DP[i][j] = DP[i - 1][j];
DP[i + 1][j] = DP[i - 1][j];
}
}else if (p[i - 1] == '.'){
DP[i][j] = DP[i - 1][j - 1];
}else if (isalpha(p[i - 1])){
if (p[i - 1] == s[j - 1]){
DP[i][j] = DP[i - 1][j - 1];
}else{
DP[i][j] = false;
}
}
// cout << i << j << DP[i][j];
}
}
return DP[m][n];
}
};
思路基本类似，使用记忆化搜索， 但是要想清楚else里面的判断
class Solution {
public:
/**
* @param s: A string
* @param p: A string includes "." and "*"
* @return: A boolean
*/
bool isMatch(string &s, string &p) {
// write your code here
unordered_map <int, bool> memo;
return matchHelper(s, 0, p, 0, memo);
}
bool matchHelper(string &s, int s_temp, string &p, int p_temp, unordered_map <int, bool> &memo){
if (memo.find(s_temp + s.size() * p_temp) != memo.end()){
return memo[s_temp + s.size() * p_temp];
}
if (s_temp == s.size() && p_temp == p.size()){
return true;
}
bool matched;
if (s_temp == s.size() && (p_temp + 1 < p.size() && p[p_temp + 1] == '*')){
matched = matchHelper(s, s_temp, p, p_temp + 2, memo);
memo[s_temp + s.size() * p_temp] = matched;
return matched;
}
if (s_temp > s.size() || p_temp >= p.size()){
return false;
}
if (p_temp == (p.size() - 1) || (p_temp + 1 < p.size() && p[p_temp + 1] != '*')){
if (charMatch(s[s_temp], p[p_temp])){
matched = matchHelper(s, s_temp + 1, p, p_temp + 1, memo);
}
}
else{
if(!charMatch(s[s_temp], p[p_temp])){
matched = matchHelper(s, s_temp, p, p_temp + 2, memo);
}
else{
matched = matchHelper(s, s_temp + 1, p, p_temp, memo) || matchHelper(s, s_temp, p, p_temp + 2, memo);
}
}
memo[s_temp + s.size() * p_temp] = matched;
return matched;
}
bool charMatch(char a, char b){
if (a == b || b == '.'){
return true;
}
return false;
}
};
110. Minimum Path Sum
class Solution {
public:
/**
* @param grid: a list of lists of integers
* @return: An integer, minimizes the sum of all numbers along its path
*/
int minPathSum(vector<vector<int>> &grid) {
// write your code here
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> sum (m, vector<int>(n, 0));
sum[0][0] = grid[0][0];
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
if (i == 0 && j > 0){
sum[i][j] = sum[i][j - 1] + grid[i][j];
}
if (i > 0 && j == 0){
sum[i][j] = sum[i - 1][j] + grid[i][j];
}
if (i > 0 && j > 0){
sum[i][j] = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
}
}
}
return sum[m - 1][n - 1];
}
};
603. Largest Divisible Subset
better version by laoshi
记录点的种类数和father
class Solution:
# @param {int[]} nums a set of distinct positive integers
# @return {int[]} the largest subset
def largestDivisibleSubset(self, nums):
# Write your code here
n = len(nums)
dp = [1] * n
father = [-1] * n
nums.sort()
m, index = 0, -1
for i in xrange(n):
for j in xrange(i):
if nums[i] % nums[j] == 0:
if 1 + dp[j] > dp[i]:
dp[i] = dp[j] + 1
father[i] = j
if dp[i] >= m:
m = dp[i]
index = i
result = []
for i in xrange(m):
result.append(nums[index])
index = father[index]
return result
my submission
class Solution {
public:
/*
* @param nums: a set of distinct positive integers
* @return: the largest subset
*/
vector<int> largestDivisibleSubset(vector<int> &nums) {
// write your code here
sort(nums.begin(), nums.end());
vector<vector<int>> res(nums.size());
for (int i = 0; i < nums.size(); i ++){
int iTemp = 0;
for (int j = 0; j < i; j ++){
if ((nums[i] % nums[j]) == 0 && res[j].size() > iTemp){
iTemp = res[j].size();
res[i] = res[j];
res[i].push_back(nums[i]);
}
}
if (iTemp == 0){
res[i].push_back(nums[i]);
}
}
int maxNum = 0;
int maxPos = 0;
for (int i = 0; i < nums.size(); i ++){
if(res[i].size() > maxNum){
maxNum = res[i].size();
maxPos = i;
}
}
return res[maxPos];
}
};
knight shortest path
遍历数组：for(auto i : nums)
class Solution {
public:
/**
* @param grid: a chessboard included 0 and 1
* @return: the shortest path
*/
int shortestPath2(vector<vector<bool>> &grid) {
// write your code here
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> d = { { -2, 1 },{ 2, 1 },{ -1, 2 },{ 1, 2 } };
vector<vector<int>> path(m, vector<int>(n, m*n));
path[0][0] = 0;
for (int j = 0; j < n - 1; j++) {
for (int i = 0; i < m; i++) {
if (grid[i][j] != 1) {
for (int k = 0; k < 4; k++) {
if (i + d[k][0] >= m || i + d[k][0] < 0 || j + d[k][1] >= n) {
continue;
}
if (grid[i + d[k][0]][j + d[k][1]] != 1 && path[i + d[k][0]][j + d[k][1]] > path[i][j] + 1) {
path[i + d[k][0]][j + d[k][1]] = path[i][j] + 1;
}
}
}
}
}
if (path[m - 1][n - 1] == m*n){
return -1;
}
return path[m - 1][n - 1];
}
};
76. Longest Increasing Subsequence
class Solution {
public:
/**
* @param nums: An integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> &nums) {
// write your code here
// if (nums.size() == 0){
// return 0;
// }
int m = nums.size();
vector<int> seq(m, INT_MAX);
for (int i = 0; i < m; i ++){
int temp = lower_bound(seq.begin(), seq.end(), nums[i]) - seq.begin();
cout << temp << endl;
seq[temp] = nums[i];
}
int temp = 0;
while(temp < m && seq[temp] != INT_MAX){
temp ++;
}
return temp;
}
};
class Solution {
public:
/**
* @param nums: An integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> &nums) {
// write your code here
if (nums.size() == 0){
return 0;
}
//存每个数为结尾的最长子序列
//vector <int> dp (nums.size());
//存储dp值为i的最小的数字
vector <int> res (nums.size() + 1);
for (int i = 1; i < nums.size() + 1; i ++){
res[i] = INT_MAX;
}
res[1] = 0;
int temp = 1;
for (int i = 0; i < nums.size(); i ++){
int index = binarySearch(nums, res, temp, i);
if (index == temp){
temp ++;
}
res[index] = nums[i];
//cout << index << ' ' << res[index]<< endl;
}
temp = 0;
for (int i = 1; i < nums.size() + 1; i ++){
if (res[i] == INT_MAX){
break;
}
temp ++;
}
return temp;
}
int binarySearch(vector <int> & nums, vector <int> &res, int temp, int i){
int start = 0, end = temp;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (res[mid] < nums[i]){
start = mid;
}else{
end = mid;
}
}
return end;
}
};
602 Russian Doll
O(n2)方法
class Solution {
public:
/*
* @param envelopes: a number of envelopes with widths and heights
* @return: the maximum number of envelopes
*/
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
// write your code here
sort(envelopes.begin(), envelopes.end());
//vector <pair<int, int>> previous(envelopes.size());
vector <int> res(envelopes.size(), 1);
for (int i = 1; i < envelopes.size(); i ++){
int temp = 1;
for(int j = 0; j < i; j ++){
if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second && res[j] + 1 > temp){
temp = res[j] + 1;
//previous[i] = envelopes[j];
}
}
res[i] = temp;
}
auto resPos = max_element(res.begin(), res.end());
return res[resPos - res.begin()];
}
};
O(nlogn)
[[4,5],[4,6],[6,7],[2,3],[1,1]]
[1,1] [2, 8][4,6][4,5] [6,7]
dp[0]=0;
height[0]=1;
dp[1]=1;
height[1]=8; 3
dp[2]=1; 2
height[1]=6; 6
dp[3]=1; 3
height[1]=5; 5
dp[4]=2; 5
height[2]=7 7
bool cmp(const pair<int,int>&x, const pair<int, int>&y) {
return x.first != y.first ? x.first < y.first : x.second > y.second;
}
class Solution {
public:
/**
* @param envelopes a number of envelopes with widths and heights
* @return the maximum number of envelopes
*/
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
// Write your code here
int n = envelopes.size();
if (n == 0) {
return 0;
}
sort(envelopes.begin(), envelopes.end(), cmp);
vector<int> dp(n), height(n+1, INT_MAX);
for (int i = 0; i < n; i++) {
int k = lower_bound(height.begin(), height.end(), envelopes[i].second) - height.begin() ;
dp[i] = k;
height[k] = envelopes[i].second;
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, dp[i]);
}
return ans + 1;
}
};
309. Best Time to Buy and Sell Stock with Cooldown
class Solution {
public:
int maxProfit(vector<int>& prices) {
int m = prices.size();
vector<int> buy(m, 0);
vector<int> sell(m, 0);
if (m == 0 || m == 1){
return 0;
}
buy[0] = - prices[0];
sell[0] = 0;
buy[1] = max(- prices[1], buy[0]);
sell[1] = max(buy[0] + prices[1], sell[0]);
for(int i = 2; i < m; i ++){
buy[i] = max(sell[i - 2] - prices[i], buy[i - 1]);
sell[i] = max(buy[i - 1] + prices[i], sell[i - 1]);
}
return sell[m - 1];
}
};
若有收获，就点个赞吧
0 人点赞
