leetcode系统性刷题（五）-----动态规划

90 阅读 0 评论 60 点赞

我是靠谱客的博主饱满学姐，这篇文章主要介绍leetcode系统性刷题（五）-----动态规划，现在分享给大家，希望可以做个参考。

一.动态规划
1.爬楼梯（70）
一看为斐波那契数列，使用相同方法求解：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int climbStairs(int n) {
if(n==1||n==2)return n;
int sum = 0;
int a = 1;
int b = 2;
while(n>2){
sum = a + b;
a = b;
b = sum;
n--;
}
return sum;
}

利用动态规划的思想递推：
关键看出：第i级台阶的爬法=第i-1级+第i-2级。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int climbStairs(int n) {
if(n==0||n==1||n==2)return n;
vector<int> dp(n+1,0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<n+1;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}

2.打家劫舍（198）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int rob(vector<int>& nums) {
if (nums.size()==0)return 0;
vector<int> dp(nums.size(),0);
if(nums.size()==1)return nums[0];
if(nums.size()==2)return max(nums[0],nums[1]);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);//注意此处
for(int i=2;i<nums.size();i++){
dp[i] = max(dp[i-1], dp[i-2]+nums[i]); //状态转移方程
//选择了第i家，则抢钱金额为dp[i-2]+nums[i]
//若不选择第i家，则为dp[i-1]
//每一步都是选择两种情况中最大的
}
return dp[nums.size()-1];
}

3.连续子数组的最大和（42，53）
基本思想和打家劫舍那题相似，每次的dp[i]都是存储当前连续的最大和。注意需要O(n)复杂度，所以最大值使用一个变量单独存储，每次更新。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int maxSubArray(vector<int>& nums) {
if (nums.size()==0)return 0;
vector<int>dp(nums.size(),0);
int max_val = nums[0];
dp[0] = nums[0];
for(int i=1;i<nums.size();i++){
dp[i] = max(dp[i-1]+nums[i],nums[i]);
max_val = max_val > dp[i] ? max_val : dp[i];
}
return max_val;
}

4.零钱兑换（322）
这里要变换思路，无法采用coins数组作为dp[i]对应，则将i设成总金额，dp[i]即为金额i对应的最少零钱个数，每个dp[i]都存储当前金额的最少零钱数。
状态转移方程：dp[i]=min( dp[i-coins[j]] ) + 1。
例如：coins=[1,2,5] amount = 5
当i = 3,dp[3] = min(dp[3-1],dp[3-2])+1
注意：1）设置min_pos每次选取dp[i-coins[j]]中的最小值
2）所选取的 dp[i-coins[j]] != -1，因为当存在与当前金额相同的零钱时，dp[i-coins[j]]=dp[0]=0,而若另外一个同样满足i-coins[j]>=0的dp[i-coins[j]]=-1,则会选择min_pos=-1,出现错误。例如coins=[2,3] amount=3. dp[1]=-1,若不限定dp[i-coins[j]] != -1，则dp[3]=min(dp[1], dp[0])+1=-1+1=0,出现错误。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,-1);
dp[0] = 0;
for(int i=1;i<amount+1;i++){
int min_pos = INT_MAX;
for(int j=0;j<coins.size();j++){
if(i-coins[j]>=0&&dp[i-coins[j]]!=-1){
min_pos = min(min_pos, dp[i-coins[j]]);
dp[i] = min_pos + 1;
}
}
//cout<<dp[i]<<endl; 
}
return dp[amount];
}

5.三角形最小路径和（120）
采用二维的dp数组，记录每个位置的最佳路径和，采用从下到上的顺序进行推导，方便处理。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 int minimumTotal(vector<vector<int>>& triangle) {
vector<vector<int>>dp;//建立最优解数组
int n = triangle.size()-1;
for(int i=0;i<triangle.size();i++){
dp.push_back(vector<int>());
for(int j=0;j<triangle[i].size();j++){
dp[i].push_back(0);
}
}
for(int i=0;i<triangle.size();i++){
dp[n][i] = triangle[n][i];
}
for(int i=n-1;i>=0;i--){
for(int j=0;j<triangle[i].size();j++){
dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j];
}
}
return dp[0][0];
}

6.使用最小花费爬楼梯（746）
设置dp[i]为爬上第i级楼梯的最小花费，因为可以选择0或者1作为初始，所以dp[0]=dp[1]=0,要爬上第i级楼梯是指要越过第i级楼梯，所以爬到顶数组下标为size，则第i级楼梯的最小花费为：
dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

复制代码

1
2
3
4
5
6
7
8
9
10
11
 int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
cout<<dp[i]<<endl;
}
return dp[n];
}

改进，使用两个变量替代vector

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
// vector<int> dp(n + 1);
int dp1 = 0;
int dp2 = 0;
int res = 0;
for (int i = 2; i <= n; i++) {
// int tem = dp2;
res = min(dp2 + cost[i - 1], dp1 + cost[i - 2]);
dp1 = dp2;
dp2 = res;
//cout<<dp[i]<<endl;
}
return res;
}

7.打家劫舍II（213）
改成环形排列，同样使用两次线性排列的解法，分为不打劫第一家和不打劫最后一家的分法。最后比较返回两种方法的最大值

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 int rob(vector<int>& nums) {
int len = nums.size();
vector<int> dp1(len,0);
vector<int> dp2(len-1,0);
if(len<=3){
sort(nums.begin(),nums.end());
return nums[len-1];
}
else{
//不抢劫第一家
dp1[0] = 0;
dp1[1] = nums[1];
for(int i=2;i<len;i++){
dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i]);
}
//不抢劫最后一家
dp2[0] = nums[0];
dp2[1] = max(dp2[0],nums[1]);//注意此处
for(int i=2;i<len-1;i++){
dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i]);
}
return max(dp1[len-1], dp2[len-2]);
}
}

8.不同路径（62）
使用二维数组动态规划，边沿的路径只有一种可能，内部的点的可能路径数等于其上和左边的数决定。dp[i][j] =dp[i][j-1]+dp[i-1][j]
注意创建二维数组为：
vector<vector<int>> dp(m,vector<int>(n,0));

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,0));
// vector<vector<int>> f(m, vector<int>(n));
for(int i=0;i<n;i++){
dp[0][i] = 1;
}
for(int i=1;i<m;i++){
dp[i][0] = 1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}

9.最小路径和（64）
和不同路径同样的套路。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
//cout<<n<<"和"<<m<<endl;
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
for(int i=1;i<n;i++){
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}

10.不同路径和II(63)
基本思路和之前相同，但注意在边界值处赋值时要注意不仅要考虑当前位置是否有障碍，还要考虑当前位置的前一个位置是否有障碍物，如果有障碍物，则只能赋值为0，不能一股脑的赋值为1.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if(obstacleGrid[0][0]==1)return 0;
obstacleGrid[0][0] = 1;
for(int i=1;i<m;i++){
if(obstacleGrid[i][0]==0&&obstacleGrid[i-1][0]==1){
obstacleGrid[i][0] = 1;
}
else if(obstacleGrid[i][0]==1){
obstacleGrid[i][0] = 0;
}
}
for(int i=1;i<n;i++){
if(obstacleGrid[0][i]==0&&obstacleGrid[0][i-1]==1){
obstacleGrid[0][i] = 1;
}
else if(obstacleGrid[0][i]==1){
obstacleGrid[0][i] = 0;
}
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(obstacleGrid[i][j]==1){
obstacleGrid[i][j] = 0;
}
else{
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
}
}
}
return obstacleGrid[m-1][n-1];
}

11.最大正方形（221）
边沿部分（i=0和j=0部分）如果为1，则等于1。中间部分则为最近的正方形三个元素中最小的一个加1.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> vc(m,vector<int>(n,0));
int maxL = 0;
int res = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='1'){
if(i==0||j==0){
vc[i][j] = 1;
}
else{
vc[i][j] = min(min(vc[i-1][j],vc[i][j-1]),vc[i-1][j-1]) + 1;
}
maxL = max(maxL,vc[i][j]);
}
}
}
res = pow(maxL,2);
return res;
}

12.完全平方数（279）
dp[i]是存放完全平方数和为i的最少的完全平方数的个数，则dp[i] = min(dp[i-jj]+1,dp[i]);(jj<i)

复制代码

1
2
3
4
5
6
7
8
9
10
11
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j*j<=i;j++){
dp[i] = min(dp[i-j*j]+1,dp[i]);
}
}
return dp[n];
}

13.最长递增子序列（300）
使用动态规划，初始化dp数组各值为1,当dp[j]<dp[i]的时候，状态转移方程为dp[i] = max(dp[i],dp[j]+1)

复制代码

1
2
3
 for(int i=1;i<len;i++){
for(int j=0;j<=i;j++)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
int val = 0;
if(len<=1)return len;
vector<int> dp(len,1);
for(int i=1;i<len;i++){
for(int j=0;j<=i;j++){
if(nums[i]>nums[j]){
dp[i] = max(dp[j]+1, dp[i]);
}
}
val = max(val,dp[i]);
}
return val;
}

14.单词拆分（139）
dp[i]代表前i个字符能否被拆分，dp[0]=false
没遍历一个字符，按照单词字典里的单词来逐个比较i-word.length能否被拆分出来,即s.substr(i-word.length,word.length)==word，如果可以拆分，就将dp[i] = dp[i-word.length] || dp[i]

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 bool wordBreak(string s, vector<string>& wordDict) {
int len = s.length();
vector<bool> dp(len+1,false);
dp[0] = true;
for(int i=1;i<=len;i++){
for(string word:wordDict){
int len1 = word.length();
if(i>=len1&&s.substr(i-len1,len1)==word){
dp[i] = dp[i-len1]||dp[i];
//要同时比较dp[i-len1]和dp[i]是因为怕出现"dogs"
//["dog","s","gs"]这种，本来在i=4的位置时为true，但再次遍历Word为gs时候，dp[4] = dp[i-len1] = false.结果不对。所以为了防止结果倒退，需要用或条件
}
}
cout<<dp[i]<<endl;
}
return dp[len];
}

15.剪绳子（剑指14-i）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int cuttingRope(int n) {
if(n<3)return 1;
vector<int> dp(n+1,0);
dp[2] = 1;
for(int i=3;i<=n;i++){
for(int j=2;j<i;j++){//从2开始切，切1对于倍数增长没有影响
dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));//j*(i-j)切一刀
//j*dp[i-j],切下来的部分继续切
}
}
return dp[n];
}

16.剑指60 n个骰子

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<double> dicesProbability(int n) {
//dp[i][j]代表i个骰子投掷点数和为j的次数,与找零钱类似的思路。
//dp[i][j] = sum(dp[i-1][j-k]) k=(1,6)
vector<vector<int>> dp(12,vector<int>(80,0));
vector<double> res;
for(int i=1;i<=6;i++){
dp[1][i] = 1;
}
for(int i=2;i<=n;i++){
for(int j=i;j<=i*6;j++){
for(int k=1;k<=6;k++){
if(j-k<=0)break;
else if(j-k>(i-1)*6)continue;
dp[i][j] += dp[i-1][j-k];
}
}
}
double re = 0;
double total = pow(6,n);
for(int i=n;i<=n*6;i++){
re = double(dp[n][i]) / total;
res.emplace_back(re);
}
return res;
}

17.区域和检索（303）
dp[i]记录的是第i个元素前的元素之和，称之为前序元素和。要求i—j之间的元素和就等于dp[j+1] - dp[i]

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumArray {
public:
NumArray(vector<int>& nums) {
data.assign(nums.begin(), nums.end());
sum = 0;
size = data.size();
dp.resize(size+1);
dp[0] = 0;
for(int i=1;i<=size;i++){
dp[i] = dp[i-1] + nums[i-1];
}
}
int sumRange(int left, int right) {
sum = dp[right+1] - dp[left];
return sum;
}
private:
vector<int> data;
int sum;
vector<int> dp;
int size;
};

18.乘积最大子数组（152）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 int maxProduct(vector<int>& nums) {
//因为正负号不定，所以当前的最优就不一定是前一个元素的最优解可以推算出的。也有可能是
//前一个元素的最差解推算得出。所以设定两个数组维护当前元素的最优解和最差解
int len = nums.size();
if(len==1)return nums[0];
vector<int> max_(len);
vector<int> min_(len);
max_[0] = nums[0];
min_[0] = nums[0];
int res = 0;
for(int i=1;i<len;i++){
max_[i] = max(max_[i-1]*nums[i],max(min_[i-1]*nums[i], nums[i]));
//每一次都考虑三种情况可能出现最优解
min_[i] = min(min_[i-1]*nums[i],min(max_[i-1]*nums[i], nums[i]));
res = max(res, max_[i]);
}
res = max(res, max_[0]);
return res;
}

19.最长公共子序列（1143）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.length();
int len2 = text2.length();
vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(text1[i-1]==text2[j-1]){ //dp[i][j]代表text1[i-1]
dp[i][j] = dp[i-1][j-1] + 1;
}
else if(text1[i-1]!=text2[j-1]){
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}
dp[i][j] 斜左上角的值表示：字符串1前i-1个位置和字符串2的前j-1个位置的最长公共子序列的值。如果s1[i] === s2[j]，表示在dp[i][j]这个位置的最长公共子序列的值是之前的值加1。如果 s1[i] !== s2[j]，那肯定是取之前的字符串1的前i-1个位置 && 字符串2的前j个位置，字符串的前i个位置 && 字符串2的前j-1个位置的最大值。

20、分割等和子集（416）----01背包问题
分为考虑当前元素num[i]和不考虑当前元素nums[i],目标值为元素之和的一半
考虑的时候：

复制代码

1
2
3
if(nums[i]==j) dp[i][j] = true;//当前nums直接就等于j
dp[i][j] = dp[i-1][j-nums[i]];	//前i-1个元素中的可可以组成j-nums[i]

不考虑的时候：

复制代码

1
2
 dp[i][j] = dp[i-1][j];

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 int Sum_(vector<int>& nums){
int sum = 0;
for(int num:nums){
sum += num;
}
return sum;
}
bool canPartition(vector<int>& nums) {
int sum = Sum_(nums);
if(sum % 2 != 0)return false;
int len = nums.size();
if(len<2)return false;
int target = sum / 2;
vector<vector<bool>> dp(len, vector<bool>(target+1, false));
if(nums[0]<target){ //注意初始化时候判断num[0]是不是大于target即列数
dp[0][nums[0]] = true;
}
for(int i=1;i<len;i++){
for(int j=0;j<=target;j++){
dp[i][j] = dp[i-1][j];
if(nums[i]==j){
dp[i][j] = true;
continue;
}
else if(j>nums[i]){//注意这里
dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j];
}//考虑当前的元素，即将当前的元素nums[i]添加到背包中
}
}
return dp[len-1][target];
}

21.LCP 07. 传递信息
dp[i][j]代表经过i轮传递传递到第j个人手中。每次要传到第j个人手中，关键是在第i-1次要能传递到第j个人的上一个人手中。
思路一：先遍历一次数组，把属于每一个人的上一个人集合到一起，每次遍历的时候考虑当前第i人的上一个人的集合。
例如：第i次要传给3，而关系数组中[1,3],[4,3]说明只有1和4能够传给3，所以就要看第i-1次有没有传给1，和4

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int numWays(int n, vector<vector<int>>& relation, int k) {
//想要传到第i个人，关键是看上一次时有没有传到第i个人的上一个人手里
//先建立一个数组存放每个人的上一个人的编号
int m = relation.size();
vector<vector<int>> last_idx(n);
for(int i=0;i<m;i++){
last_idx[relation[i][1]].push_back(relation[i][0]);//把每一个人的上一个人的编号存储到一起
}
cout<<last_idx.size()<<endl;
vector<vector<int>> dp(k+1,vector<int>(n, 0));
dp[0][0] = 1;
for(int i=1;i<=k;i++){
for(int j=0;j<n;j++){
for(int it:last_idx[j]){
dp[i][j] = dp[i-1][it] + dp[i][j];
}
}
}
return dp[k][n-1];
}

这里其实不需要采用结果集合的顺序进行遍历，因为关系数组中的第二位的分为就是人的编号范围

复制代码

1
2
3
4
5
6
7
8
9
 vector<vector<int>> dp(k+1,vector<int>(n, 0));
dp[0][0] = 1;
//改进:遍历的时候不采用结果集合进行遍历
for(int i=1;i<=k;i++){
for(auto it:relation){
dp[i][it[1]] += dp[i-1][it[0]];
}
}

二、位运算
1.颠倒二进制位（190）
二进制数取余及取商操作类比10进制进行，只需将2写成10就可以看出来了。

复制代码

1
2
3
4
5
6
7
8
9
10
 uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for(int i=0;i<32;i++){
int num = n%2;
res += num * pow(2,31-i);
n = n / 2;
}
return res;
}