DP刷题练习（一）

作者：blue

时间：2024.8.5

文章内容学习自代码随想录，感谢carl！！！！

509. 斐波那契数 - 力扣（LeetCode）

int fib(int n) {
   
        int dp[31];//dp[i]表示第i个数的值
        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. 爬楼梯 - 力扣（LeetCode）

int climbStairs(int n) {
   
        int dp[46];//dp[i]表示，爬到第i层楼梯，有dp[i]种方案
        dp[1]=1,dp[2]=2;
        for(int i=3;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
        return dp[n];
    }
//递推公式怎么来？
//你想上到第10层，那你前一步是什么？
//肯定你是从第9层爬一步或者是从第8层爬两步上来，那么爬上第10层的方案就是，爬上第9层的方案+爬上第8层的方案
//∴dp[i]=dp[i-1]+dp[i-2],将最初始的dp[1]=1,dp[2]=2;

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

int minCostClimbingStairs(vector<int>& cost) {
   
        int n=cost.size();
        int dp[n+1];//dp[i]表示，爬到第i层的最小花费
        dp[0]=0,dp[1]=0;//如果是爬到0/1就不用钱，因为0/1都可以作为初始点
        for(int i=2;i<=n;i++){
   
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];//顶楼是n
    }

//要注意题目的要求，题目是说，你一次花费当下这一层，注意是当层！的钱，你就可以向上爬1/2层
//所以你爬到第i层，可以是从i-1层来花费cost[i-1]，也可以是从i-2层来花费cost[i-2],二者取最小值就是爬上第i层的最小花费
//所以递推公式就是 dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
//要注意dp数组的初始化，你可以选择从第0层和第1层开始爬，所以爬到第0/1层的花费都是0

62. 不同路径 - 力扣（LeetCode）

 int uniquePaths(int m, int n) {
   
        int dp[m][n];//dp[i][j]表示从起点(0,0)走到(i,j)的不同路径数
        dp[0][0]=1;
        for(int i=1;i<=n-1;i++) dp[0][i]=1;
        for(int i=1;i<=m-1;i++) dp[i][0]=1;
        for(int i=1;i<=m-1;i++)
        {
   
            for(int j=1;j<=n-1;j++) dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
        return dp[m-1][n-1];
    }
//动态规划五步曲
//dp含义：dp[i][j]表示从起点(0,0)走到(i,j)的不同路径数

//递推公式；dp[i][j]=dp[i-1][j]+dp[i][j-1],为什么是这样，你想，你每一步只能从上方一格，或者是左方一格走来
//那么这一格的方案数，不就是上方一格的dp[i-1][j]加上左方一格的dp[i][j-1]

//初始化：你想第一行往右的这一排，是不是只能从第一格往右走走到，那他们的路径数不就只能是从左往右吗？所以初始化为1
//同理你你一列往下这一排只能从第一格往下走走到，那他们的路径数不就只能是从上往下吗？所以初始化为1
//那对于(0,0)呢？也是只能是1，你不走就已经到达终点不也是一种方案吗？

//遍历顺序：自不必多说，先知道前面的才能知道后面的，所以是从前往后遍历

63. 不同路径 II - 力扣（LeetCode）

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
   
        int m=obstacleGrid.size();int n=obstacleGrid[0].size();//获取行和列的长度
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return 0;//如果障碍物在起点或者终点，那路径数无论如何都是0
        int dp[m+10][n+10];
        dp[0][0]=1;
        int i;
        for(i=1;i<=n-1;i++){
   //行初始化
            if(obstacleGrid[0][i]==0) dp[0][i]=1;
            else break;
        }
        for(int j=i;j<=n-1;j++) dp[0][j]=0;
//////////////////////////////////////////////////////
         for(i=1;i<=m-1;i++){
   //列初始化
            if(obstacleGrid[i][0]==0) dp[i][0]=1;
            else break;
        }
        for(int j=i;j<=m-1;j++) dp[j][0]=0;
/////////////////////////////////////////////////////
        for(int j=1;j<=m-1;j++)
        {
   
            for(int k=1;k<=n-1;k++){
   
                if(obstacleGrid[j][k]==0) dp[j][k]=dp[j-1][k]+dp[j][k-1];
                else dp[j][k]=0;
            }
        }
        return dp[m-1][n-1];
    }


//别看本题代码写的如此多，其实并不复杂，我们一步一步来分析
//还是动规五步曲，在这里我设obs为障碍物数组
//dp含义：dp[i][j]表示从(0,0)->(i,j)的不同路径数

//递推公式：①obs[i][j]==0时 dp[i][j]=dp[i-1][j]+dp[i][j-1]
//         ②obs[i][j]==1时 dp[i][j]=0

//初始化：以上两步和上道题大同小异，本题初始化才是最讲究的部分
//首先如果终点或者起点就已经是障碍物了，那么肯定出发不了，肯定到达不了，路径数就是0，直接返回0即可
//其次第一行和第一列依然是最特殊的，在没有遇到障碍物之前，第一行/列上的这些点都是可达的，直接初始化dp[0][i]/dp[i][0]=1
//但是一旦遇到了障碍物，那么障碍物后面点都是不可达的，为什么？不要忘记了题目说的，你只能向右或者向下走！所以第一行只能从右来
//你一旦遇到障碍物，后面就不能到达了，同理，第一列也一样
//所以一旦遇到障碍物，我们就初始化障碍物的位置及其后面的位置的方案数为0！！！

//遍历顺序：自然也是从前往后，因为只有前面的先知道了，后面的才能知道！！！！！

343. 整数拆分 - 力扣（LeetCode）

数的拆分是dp中常见的类型

1.dp数组的含义：dp[i]表示，将i拆分，得到的最大值为dp[i]

2.递推公式：我们固定j（从1开始枚举到i-1），那么针对每一种情况，我们都可以将其拆分为2个数，或者是n个数的乘积

为什么这样分呢?因为拆成两个数是最基本的，n个数可以递归得到

int a=j*(i-j);//拆两个数
int b=j*dp[i-j];//拆两个数以上，递归思想！
//所以我的递推公式就是
dp[i]=max(dp[i],max(a,b));
//为什么要将dp[i]也放进来比较，因为我们是枚举j，也就是枚举拆分的第一位数！这有多种情况，而我们要的是最大的那个！

3.初始化：

0与1不必说，不用拆分，自然初始化为0

dp[2]=1,的话无法用之前的基础步得到，所以2也得初始化

//3可以拆成，1*2，1*dp[2]，2*1，2*dp[1] 所以3可以由之前的情况得到故3不用初始化

dp[0]=0,dp[1]=0;//无法拆分
 dp[2]=1;//只能拆1*1

4.遍历顺序：自是从前往后，先知道前面的才能知道后面的

 int integerBreak(int n) {
   
        int dp[n+10];
        memset(dp,0,sizeof(dp));//注意这里先给所有赋值为0，因为我们一开始用dp[i]去比较，dp[i]中是没有值的，这样会报错
        dp[0]=0,dp[1]=0;//无法拆分
        dp[2]=1;//只能拆1*1
        for(int i=3;i<=n;i++)
        {
   
            for(int j=1;j<i;j++)
            {
   
                int a=j*(i-j);//拆两个数
                int b=j*dp[i-j];//拆两个数以上，递归思想！
                dp[i]=max(dp[i],max(a,b));
            }
        }
        return dp[n];
    }

小优化：

我们将数拆分，然后要使拆分后这些数的乘积最大，那么我们就要尽量使这些数相等，所以你拆一半就够了，后面你拆数就是向着大小差异的极端去的，所以可以这样优化

for(int j=1;j<=i/2;j++)

int integerBreak(int n) {
   
        int dp[n+10];
        memset(dp,0,sizeof(dp));
        dp[0]=0,dp[1]=0;//无法拆分
        dp[2]=1;//只能拆1*1
        for(int i=3;i<=n;i++)
        {
   
            for(int j=1;j<=i/2;j++)
            {
   
                int a=j*(i-j);//拆两个数
                int b=j*dp[i-j];//拆两个数以上，递归思想！
                dp[i]=max(dp[i],max(a,b));
            }
        }
        return dp[n];
    }

96. 不同的二叉搜索树 - 力扣（LeetCode）

首先何为二叉搜索树，节点的要求是针对于顶点来说，顶点左侧要小于顶点，顶点的右侧要大于顶点，就是要满足左小右大

1.dp数组的含义：dp[i]，表示节点数目为i时，共有dp[i]种不同的二叉搜索树

2.递推公式：我们先用i枚举节点个数，用j表示j节点作为二叉搜索树的顶点为j，那么想想看，我们如何计算以j为顶点的二叉搜索树的种数呢？

是不是左子树的种数*右子树的种数，那么左子树有几种？是不是dp[j-1]种，你就想一串数，1，2，3，4，5此时j=4，那么比4小的，不就只有3个节点，而比4大的，不就是节点总数i，减掉j，5-4=1

然后j，有i种情况，就是说每个节点都可以作为顶点，所以都要把这i种情况累加起来

于是状态转移方程：dp[i]+=dp[j-1]*dp[i-j]

3.初始化：dp[0]=1,为什么？空树也是二叉搜索树！！

dp[1]要不要初始化？dp[1]+=dp[0]*dp[0]=1,符合现实情况，可以由递推公式得到，所以不用初始化

int numTrees(int n) {
   
        int dp[n+10];//表示i个节点，有dp[i]种不同的二叉搜索树
        memset(dp,0,sizeof(dp));//因为一会要自加，所以先给初值赋0
        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];//dp[j-1]左子树总数
            }                          //dp[i-j]右子树总数
        }
        return dp[n];
    }

416. 分割等和子集 - 力扣（LeetCode）这个背包能不能装满？？？

class Solution {
   
public:
    bool canPartition(vector<int>& nums) {
   
        int n=0;//背包容量
        int sum=0;
        int m=nums.size();//物品数量
        for(int i=0;i<m;i++) sum+=nums[i];
        n=sum/2;
        if(sum-n!=n) return false;//特判，不可能等分的情况
        int dp[m][n+1];//dp[i][j]针对前（0-i）个物品用容量j的背包来存放能否放满
        //初始化
        for(int i=0;i<m;i++) dp[i][0]=0;//容量为0什么都放不了
        for(int i=0;i<=n;i++){
   //第0个物品放置情况
            if(i>=nums[0]) dp[0][i]=nums[0];
            else dp[0][i]=0;
        }

        for(int i=1;i<m;i++){
   //物品
            for(int j=1;j<=n;j++){
   //容量
                if(j>=nums[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                else dp[i][j]=dp[i-1][j];
            }
        }

        if(dp[m-1][n]==n) return true;
        else return false;
    }
};

学有余力，手撕01背包：P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

0/1背包要注意，所有的物品只能选择一次！！！

二维数组版本：

#include <iostream>
using namespace std;
int dp[110][1010];//dp[i][j]表示在j时间内任采（0，i）株草药可以获得的最大价值 
int t[110],m[110];
int main()
{
   
    int T,M;
    cin>>T>>M;
    for(int i=0;i<M;i++) cin>>t[i]>>m[i];

    //初始化：非常重要！！！ 
    for(int i=0;i<M;i++) dp[i][0]=0;//0秒什么都放不了 

    for(int i=0;i<=T;i++){
    //注意时间可以到达第T秒 
        if(i>=t[0]) dp[0][i]=m[0]; //看下第一个物品能不能放 
        else dp[0][i]=0;
    }

    for(int i=1;i<M;i++){
    
        for(int j=1;j<=T;j++){
    //注意时间可以到达第T秒 
            if(j>=t[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+m[i]);//能放，看下放值不值 
            else dp[i][j]=dp[i-1][j];//没法放 
        }
    }

    cout<<dp[M-1][T];//注意时间可以到达第T秒 

    return 0;    
}

交替滚动版本：

经过观察可以发现，dp[i][j]的更新只与dp[i-1]的状态有关，那么我们只保留两行就够了，每一次根据第一行来更新第二行的信息，然后再把第二行替换为第一行。

#include <iostream>
using namespace std;
int dp[2][1010];//dp[0/1][j]表示在j时间内可以获得的最大价值
//0表示旧数据，1表示新数据 
int t[110],m[110];
int main()
{
   
    int T,M;
    cin>>T>>M;
    for(int i=0;i<M;i++) cin>>t[i]>>m[i];

    //初始化：非常重要！！！ 

    for(int i=0;i<=T;i++){
    //注意时间可以到达第T秒 
        if(i>=t[0]) dp[0][i]=m[0]; //看下第0个物品能不能放 
        else dp[0][i]=0;
    }

    int now=0,old=1;//我这样写是为了使代码具有一般性 

    for(int i=1;i<M;i++){
    
        swap(old,now);//新老交替
        for(int j=1;j<=T;j++){
    //注意时间可以到达第T秒 
            if(j>=t[i]) dp[now][j]=max(dp[old][j],dp[old][j-t[i]]+m[i]);//能放，看下放值不值 
            else dp[now][j]=dp[old][j];//没法放 
        }
    }

    cout<<dp[now][T];//注意时间可以到达第T秒 

    return 0;    
}

一维数组版本：

/*这里的遍历顺序非常有考究，首先为什么时间是从右往左遍历呢？
dp[i][j]的更新只与dp[i-1][j]和dp[i-1][j-weight_i]左上角这两个数据有关，而与右边的数据无关，
那么从右向左遍历，遍历时左边的数据还是上一行的数据没有更新，这样我们就可以实现自我滚动，为什么j到t[i]就可停下来，因为只有j>=t[i]时才有可能交换，而j<t[i]时保留原来的值就可以了
为什么，要先物品后时间呢？
如果你先时间后物品，你看你每次dp[j]里的值，不就永远只有1个物品吗？你每次上个物品的值都被这次的替换了，脱离了我们
dp[j]的含义！！！！*/
#include <iostream>
using namespace std;
int dp[1010];//dp[j]表示在j时间内可以获得的最大价值

int t[110],m[110];
int main()
{
   
    int T,M;
    cin>>T>>M;
    for(int i=0;i<M;i++) cin>>t[i]>>m[i];

    //初始化：非常重要！！！ 

    for(int i=0;i<=T;i++){
    //注意时间可以到达第T秒 
        if(i>=t[0]) dp[i]=m[0]; //看下第0个物品能不能放 
        else dp[i]=0;
    }


    for(int i=1;i<M;i++){
    //先物品后时间
        for(int j=T;j>=t[i];j--){
    //注意时间可以到达第T秒 
            dp[j]=max(dp[j],dp[j-t[i]]+m[i]);
        }
    }

    cout<<dp[T];//注意时间可以到达第T秒 

    return 0;    
}