力扣刷题笔记——动态规划网站首页 学无止境

力扣刷题笔记——动态规划

木子南的翻斗花园 2024-08-16 00:01:02

简介力扣刷题笔记——动态规划

动态规划基础

简称DP，如果某⼀问题有很多重叠⼦问题，使⽤动态规划是最有效的。

动态规划中每⼀个状态⼀定是由上⼀个状态推导出来的

1. 确定dp 数组（ dp table ）以及下标的含义

2. 确定递推公式

3. dp 数组如何初始化

4. 确定遍历顺序

5. 举例推导 dp 数组

509. 斐波那契数

509. 斐波那契数 - 力扣（LeetCode）https://leetcode.cn/problems/fibonacci-number/

首先思考dp数组的含义：

dp[i]是指数组中第i个数的值

状态转移方程：dp[i]=dp[i-1]+dp[i-2]

初始化：初始第1和第2个数

确定遍历顺序从头开始到第n个

举例推导dp[i] = dp[i - 1] + dp[i - 2]

class Solution {
public:
 int fib(int N) {
     if (N <= 1) return N;
     vector<int> dp(N + 1);
     dp[0] = 0;
     dp[1] = 1;
     for (int i = 2; i <= N; i++) {
     dp[i] = dp[i - 1] + dp[i - 2];
     }
     return dp[N];
}
};

70.爬楼梯

70. 爬楼梯 - 力扣（LeetCode）https://leetcode.cn/problems/climbing-stairs/

首先思考dp数组得含义：

dp[i]是指爬到第i阶有几种方法

dp[i]=dp[i-1] + dp[i-2]

初始化：初始第1和第2个数

确定遍历顺序从头开始到第n个

举例推导dp[i] = dp[i - 1] + dp[i - 2]

class Solution {
public:
    int climbStairs(int n) {

        if(n<=2){
            return n;   
        }
        vector<int> vec(n+1,0);
        vec[1]=1;
        vec[2]=2;
        for(int i=3;i<=n;i++){
            vec[i]=vec[i-1]+vec[i-2];
        }        

        return vec[n];
    }
};

746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）https://leetcode.cn/problems/min-cost-climbing-stairs/submissions/

dp[i]表示到达第i个台阶最小的花费

dp[i]=min(dp[i-1],dp[i-2])+cost[i];

初始化dp[0]=cost[0] dp[1]=cost[1]

顺序是从第2个台阶开始

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size(),0);    
        //初始化数组
        dp[0]=cost[0];
        dp[1]=cost[1];
        for(int i=2;i<cost.size();i++){
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
        return min(dp[cost.size()-1],dp[cost.size()-2]);
    }
};

62.不同路径

62. 不同路径 - 力扣（LeetCode）https://leetcode.cn/problems/unique-paths/

本题需要记录每个位置的可以到达的路径的数目

dp[i][j]表示到达第i行第j列的点的路径

dp[i][j]=dp[i-1][j]+dp[i][j-1] 每一个位置，可以通过上面和左边的位置前进一步得到

初始化明显dp[i][0]=1 dp[0][j]=1 表示第一行和第一列的到达的路径都为1

遍历的顺序从每层一层一层遍历

class Solution {
public:
int uniquePaths(int m, int n) {
	vector<vector<int>>  dp(m, vector<int>(n, 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];
}
};

63.不同的路径II

63. 不同路径 II - 力扣（LeetCode）https://leetcode.cn/problems/unique-paths-ii/

本体相对于上一题，中间多了路障

在初始化地图时，我们需要将有障碍的地方识别出来

对于每一个点，都可以通过上面或者左边的节点过来

状态转移方程：grid[i][j]=grid[i-1][j]+grid[i][j-1]

初始化：第一行和第一列每一个元素初始化为1

顺序：每一行不停的向下遍历

最后返回grid[obstacledGrid.size()][obstacleGrid[0].size()]

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n=obstacleGrid.size();
        int m=obstacleGrid[0].size();
        vector<vector<int>>  grid(n,vector<int>(m,0));
        //初始化数组 第一行和第一列可以到达的路径都是1
        for(int i=0;i<n&&obstacleGrid[i][0]==0;i++) grid[i][0]=1;
        for(int j=0;j<m&&obstacleGrid[0][j]==0;j++) grid[0][j]=1;

        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(obstacleGrid[i][j]==1) continue;
                grid[i][j]=grid[i-1][j]+grid[i][j-1];
            }
        }


        return grid[n-1][m-1];
    }
};

343 整数拆分

343. 整数拆分 - 力扣（LeetCode）https://leetcode.cn/problems/integer-break/

dp[i]表示i拆分的最大的乘积

递推公式（状态转移公式）：遍历之前的dp数据 dp[i]=max(dp[i],max(dp[i-j]*j,j*(i-j)));

dp[i]很小（起一个迭代的作用），因此取最大值基本都是后一个max中的值（dp[i-j]表示i-j拆分成的最大乘积，如果这个树乘以j大，那么不断循环，到i-1的情况，就可以找出i拆分的最大的值）

初始化，对于0和1没法拆分，那么最大的乘积为0

顺序：从1开始，从前往后

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i-1;j++){
                dp[i]=max(dp[i],max(dp[i-j]*j,j*(i-j)));
            }
        }
        return dp[n];
    }
};

96.不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）https://leetcode.cn/problems/unique-binary-search-trees/

dp[n] 一维的数组，思考含义i表示i个元素可以构成的二叉搜索树的个数

状态转移：dp[i]+=dp[j-1][i-j] (j的范围为1到i)

初始化思考i为0的情况：0个元素构成的搜索树可以直接看成一个二叉搜索树dp[0]=1

顺序：从第一个节点开始，直到第n个节点

返回 dp[n];

为什么是乘法呢，因为左右子树相当于不同的选择步骤

因此，最终的结果的个数应该是两者的乘积

class Solution {
public:
    int numTrees(int n) {
        
        //dp[i]为i个节点时，二叉搜索树的中枢
        vector<int> dp(n+1);
        dp[0]=1;
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }

        return dp[n];
    }

};

背包问题

背包问题是动态规划经典的问题，包含01背包，完全背包，多重背包等子问题

0-1背包问题

有 N 件物品和⼀个最多能被重量为 W 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是

value[i] 。每件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤。

总结一下，就是把给定的物品向背包里装，求出能够装进去的最大价值

定义一个数组int dp[i][j] ，i和物品的数量一样 j为背包的最大容量

dp[i][j] 为在容量为j的情况下，前i个物品合理装进去能够获得的最大的价值

转移公式： dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);

初始化：对于j取j<value[0]是为0，如果j>value[0],则为value[0];

int main(){
    vector<vector<int>> dp(weight.size()+1,vector<int>(rongliang+1,0));
    //全部初始化为0
    for(int j=value[0];j<=rongliang;j++){
        dp[0][j]=value[0];
    }
    for(int i=1;i<weight.size();i++){
        for(int j=0;j<=rongliang;j++){
            if(j<weight[i]) dp[i][j]=dp[i-1][j];
            else
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-weight[i]] + value[i]);    
        }
    }

    cout << dp[weight.size() - 1][bagWeight] << endl;
}

#include<iostream>
#include<vector>

using namespace std;

int main() {
	int sum, rongliang;
	cin >> sum >> rongliang;
	vector<int>  tiji(sum+1, 0);
	vector<int>  jiazhi(sum+1, 0);
	for (int i = 1; i <= sum; i++) {
		cin >> tiji[i] >> jiazhi[i];
	}

	//初始化dp数组
	vector<vector<int>> dp(sum + 1, vector<int>(rongliang + 1, 0));

	//进行动态规划
	for (int i = 1; i <= sum; i++) {
		for (int j = rongliang; j >= 0; j--) {
			//状态转移方程
			if (j >= tiji[i]) {
				//装得下
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - tiji[i]] + jiazhi[i]);
			}
			else {
				//装不下
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[sum][rongliang];
	return 0;
}

这两份代码不同：

第一：价值和重量数组的起始位置不同

第二：在第二轮循环中，第二个程序从大到小

起始位置不同，导致了初始化的过程不同，第二个不需要初始化，初始化化的过程包含在循环中

因为dp的值都是从上一行的状态转移过来的，那么就是说我们不要在意遍历的顺序，那么从开始到最后，从最后到开始都是一样的，我们依旧可以从容量开始，不断递减

思考如何简化问题的求解

使用一位动态数组就可以解决问题

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);

如果说把dp[i-1]的那一层拷贝到i层，表达式就可以是dp[i][j]=max(dp[i][j],dp[i][j-weight[i]]+value[i]);

只是用一维数组，只使用dp[j]

416.分割等和子集

416. 分割等和子集 - 力扣（LeetCode）https://leetcode.cn/problems/partition-equal-subset-sum/

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        int sum=0;
        vector<int> dp(10001,0);
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        int target=sum/2;
        
        for(int i=0;i<nums.size();i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        } 


        if(dp[target]==target) return true; 
        return false;
    }
};

分割子集，找到和相同的子集

分半，找到容量最大的；

dp数组含义，容量为i时，取得数组元素和的最大值

dp[i]=max(dp[i],dp[i-nums[i]]+nums[i])

初始化，当容量小于最小的数组元素时，dp为零，因此初始化为全零

1049. 最后一块石头的重量II

1049. 最后一块石头的重量 II - 力扣（LeetCode）https://leetcode.cn/problems/last-stone-weight-ii/

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
    
        for(int i=0;i<stones.size();i++){
            sum+=stones[i];
        }
        vector<int> vec(150001,0);
        int target=sum/2;

        for(int i=0;i<stones.size();i++){
            for(int j=target;j>=stones[i];j--){
                vec[j]=max(vec[j],vec[j-stones[i]]+stones[i]);
            }
        }

        return sum-vec[target]-vec[target];
    }
};

思考本题：
总数分半，获得容量最大可能性

sum-dp[target]-dp[target];

sum-dp[target]一定大于dp[target]

494、目标和

494. 目标和 - 力扣（LeetCode）https://leetcode.cn/problems/target-sum/

在数字前面加+-号得到目标和的数

就是装够特定容量大小的东西，总共有几种装法

dp[j]+=dp[j-nums[i]]

遍历的顺序和01背包问题一样

初始化：通过状态转移方程可以得出，当为0时，代表结果为0的时候有几种方案

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {

        int sum=0;
        for(auto i:nums){
            sum+=i;
        }
        if(target>sum) return 0;
        if((target+sum)%2==1) return 0;

        int nice=(target+sum)/2;

        vector<int> vec(1001,0);
        vec[0]=1;
        for(int i=0;i<nums.size();i++){
            for(int j=nice;j>=nums[i];j--){
                vec[j]+=vec[j-nums[i]];
            }
        }
        return vec[nice];
    }
};

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。