动态规划是分治思想的延伸,通俗一点来说就是大事化小,小事化无的艺术。
在将大问题化解为小问题的分治过程中,保存对这些小问题已经处理好的结果,并供后面处理更大规模的问题时直接使用这些结果。
动态规划的本质,是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。
状态定义的要求:定义的状态一定要形成递推关系。
一句话概括:三特点四要素两本质。
适用场景:最大值/最小值, 可不可行, 是不是,方案个数。
class Solution {
public:
int Fibonacci(int n)
{
/*if(n==0||n==1) { return n; } else { return Fibonacci(n-1)+Fibonacci(n-2); }*/
if(n==0||n==1)
{
return n;
}
int n1=0;
int n2=1;
int n3=0;
while(n>1)
{
n3=(n1+n2)%1000000007;
n1=n2;
n2=n3;
n--;
}
return n3;
}
};
class Solution {
public:
int jumpFloorII(int number)
{
if(number==0||number==1)
{
return number;
}
else
{
int ret=1;
while(number>1)
{
ret=ret*2;
number--;
}
return ret;
}
}
};
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array)
{
if(array.size()==0)
{
return 0;
}
int sum=array[0];
for(int i=0;i<array.size();i++)
{
array[i]=max(array[i-1]+array[i],array[i]);
sum=max(sum,array[i]);
}
return sum;
}
};
单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词,说明就是一个完全背包!
动规五部曲分析如下:
确定dp数组以及下标的含义:
dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。
1.
确定递推公式:
如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
那么dp[0]有没有意义呢?
dp[0]表示如果字符串为空的话,说明出现在字典里。
但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
还要讨论两层for循环的前后循序。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
本题最终要求的是是否都出现过,所以对出现单词集合里的元素是组合还是排列,并不在意!那么本题使用求排列的方式,还是求组合的方式都可以。
即:外层for循环遍历物品,内层for遍历背包 或者 外层for遍历背包,内层for循环遍历物品 都是可以的。
但本题还有特殊性,因为是要求子串,最好是遍历背包放在外循环,将遍历物品放在内循环。
如果要是外层for循环遍历物品,内层for遍历背包,就需要把所有的子串都预先放在一个容器里。(如果不理解的话,可以自己尝试这么写一写就理解了)。
所以最终我选择的遍历顺序为:遍历背包放在外循环,将遍历物品放在内循环。内循环从前到后。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
vector<bool> dp(s.size()+1,false);
dp[0]=true;
for(int i=1;i<=s.size();i++) //遍历背包
{
for(int j=0;j<i;j++) //遍历物品
{
string word=s.substr(j,i-j); //substr(起始位置,截取的个数)
{
if(dp[j]&&wordSet.find(word)!=wordSet.end())
{
dp[i]=true;
}
}
}
}
return dp[s.size()];
}
};
普通解法:
动规做法:
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle)
{
if(triangle.empty())
{
return 0;
}
int row=triangle.size(); //行数
//起始位置(row-1,j)已经确定过了
//返回结果,最上面也就是开始的地方[0][0];
for(int i=row-2;i>=0;i--)
{
for(int j=0;j<=i;j++)
{
triangle[i][j]=min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
}
}
return triangle[0][0];
}
};
class Solution {
public:
/** * * @param m int整型 * @param n int整型 * @return int整型 */
int uniquePaths(int m, int n)
{
// write code here
if(m<1||n<1)
{
return 0;
}
vector<vector<int>> pathNum(m,vector<int>(n,1));
for(int i=1;i<m;i++ )
{
for(int j=1;j<n;j++)
{
pathNum[i][j]=pathNum[i-1][j]+pathNum[i][j-1];
}
}
return pathNum[m-1][n-1];
}
};
class Solution {
public:
/** * * @param obstacleGrid int整型vector<vector<>> * @return int整型 */
int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)
{
// write code here
if(obstacleGrid.empty())
{
return 0;
}
int row=obstacleGrid.size();
int col=obstacleGrid[0].size();
vector<vector<int>> pathNum(row,vector<int>(col,0));
for(int i=0;i<row;i++)
{
if(obstacleGrid[i][0]==0)
{
pathNum[i][0]=1;
}
else
{
break;
}
}
for(int j=0;j<col;j++)
{
if(obstacleGrid[0][j]==0)
{
pathNum[0][j]=1;
}
else
{
break;
}
}
for(int i=1;i<row;i++)
{
for(int j=1;j<col;j++)
{
if(obstacleGrid[i][j]==0)
{
pathNum[i][j]=pathNum[i-1][j]+pathNum[i][j-1];
}
}
}
return pathNum[row-1][col-1];
}
};
class Solution {
public:
/** * * @param grid int整型vector<vector<>> * @return int整型 */
int minPathSum(vector<vector<int> >& grid)
{
// write code here
if(grid.size()==0)
{
return 0;
}
int row=grid.size();
int col=grid[0].size();
for(int i=1;i<row;i++)
{
grid[i][0]=grid[i-1][0]+grid[i][0];
}
for(int j=1;j<col;j++)
{
grid[0][j]=grid[0][j-1]+grid[0][j];
}
for(int i=1;i<row;i++)
{
for(int j=1;j<col;j++)
{
grid[i][j]=min(grid[i-1][j],grid[i][j-1])+grid[i][j];
}
}
return grid[row-1][col-1];
}
};
class Solution {
public:
/** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @param V: Given n items with value V[i] * @return: The maximum value */
int backPackII(int m, vector<int> &A, vector<int> &V)
{
// write your code here
int n=A.size();
if(n==0||m==0)
{
return 0;
}
vector<int> maxV(m+1,0);
for(int i=1;i<=n;i++)
{
for(int j=m;j>0;j--)
{
if(A[i-1]<=j)
{
maxV[j]=max(maxV[j],maxV[j-A[i-1]]+V[i-1]);
}
}
}
return maxV[m];
}
};
class Solution {
public:
bool isPal(string& s,int start,int end)
{
while(start<end)
{
if(s[start]!=s[end])
{
return false;
}
start++;
end--;
}
return true;
}
int minCut(string s)
{
// write code here
vector<int> minC(s.size()+1);
for(int i=1;i<=s.size();i++)
{
minC[i]=i-1;
}
for(int i=2;i<=s.size();i++)
{
//判断整体
if(isPal(s, 0, i-1))
{
minC[i]=0;
continue;
}
for(int j=1;j<i;j++) //从1开始的
{
//j<i &&[j+1,i]
if(isPal(s, j,i-1))
{
minC[i]=min(minC[i],minC[j]+1);
}
}
}
return minC[s.size()];
}
};
class Solution {
public:
int minDistance(string word1, string word2)
{
// write code here
int len1=word1.size();
int len2=word2.size();
vector<vector<int>> minD(len1+1,vector<int>(len2+1,0));
for(int i=1;i<=len2;i++)
{
minD[0][i]=i;
}
for(int i=1;i<=len1;i++)
{
minD[i][0]=i;
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
//插入、删除
minD[i][j]=min(minD[i][j-1],minD[i-1][j])+1;
//替换
if(word1[i-1]==word2[j-1])
{
minD[i][j]=min(minD[i][j],minD[i-1][j-1]);
}
else
{
minD[i][j]=min(minD[i][j],minD[i-1][j-1]+1);
}
}
}
return minD[len1][len2];
}
};
class Solution {
public:
int numDistinct(string S, string T)
{
// write code here
int len1=S.size();
int len2=T.size();
vector<vector<int>> numD(len1+1,vector<int>(len2+1,0));
//F(i,0)=1;
for(int i=0;i<=len1;i++)
{
numD[i][0]=1;
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(S[i-1]==T[j-1])
{
numD[i][j]=numD[i-1][j-1]+numD[i-1][j];
}
else
{
numD[i][j]=numD[i-1][j];
}
}
}
return numD[len1][len2];
}
};
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_44918090/article/details/120398870
内容来源于网络,如有侵权,请联系作者删除!