跳到主要内容

dp

0 说明

  • 此章节代码主要使用cpp
  • 此章节主要题目来源为leetcode

1 dp简介

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

此处不需要细究，使用题目练一下手就知道了。

PS:要了解更多关于dp的知识，可以参考代码随想录的动态规划理论基础

2 直接题目上手

此处参考代码随想录的思维导图进行训练。 图如下： 思维导图

2.1 基础题目​

2.1.1 斐波那契数列​

link:斐波那契数列 参考代码如下：

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

最基本的dp了，没什么好说的。

2.1.2 爬楼梯​

link:爬楼梯 参考代码如下：

class Solution 
{
public:
    int climbStairs(int n) 
    {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) 
        {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

稍有有变化，还是没什么好说的。

2.1.3 不同路径​

link:不同路径 参考代码入下：

class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
        if (m > n) {
            swap(m, n);
        }
        long long result = 1;
        // 计算组合数 C(m + n - 2, m - 1)
        for (int i = 1; i < m; ++i) {
            result = result * (m + n - 1 - i) / i;
        }
        return result;
    }
};

这个题我感觉更像一个数学题，求组合数的那种。

2.1.4 整数拆分​

link:整数拆分 参考代码如下：

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 / 2; j++) 
            {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];   
    }
};

2.2 背包问题​

背包问题思维导图

2.2.1 携带研究材料​

link:携带研究材料 解答代码如下：

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    vector<pair<int,int>> things(m);
    for(int i=0;i<m;i++)
    {
        cin>>things[i].first;
    }
    for(int i=0;i<m;i++)
    {
        cin>>things[i].second;
    }
    sort(things.begin(),things.end(),[](pair<int,int> a,pair<int,int> b){
        if(a.first!=b.first)
        {
            return a.first<b.first;
        }
        else
        {
            return a.second<b.second;
        }
    });
    vector<int> dp(n+1,0);
    for (int i = 0; i < m; ++i) 
    {
        for (int j = n; j >= things[i].first; --j) 
        {
            dp[j] = max(dp[j], dp[j - things[i].first] + things[i].second);
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

本题是经典的 01 背包问题。 状态定义：dp[j] 表示在背包容量为 j 时，能够装入物品的最大总价值。 状态转移：对于每一个物品，我们有两种选择： 不选：保持当前容量 j 下的最大价值不变，即 dp[j]。 选：如果当前容量 j 能装下该物品（j >= weight），则价值为 dp[j - weight] + value。 取两者的最大值：dp[j] = max(dp[j], dp[j - weight] + value)。 空间优化：使用一维数组 dp，并通过倒序遍历容量，确保每个物品只被选取一次。

2.2.2 最后一块石头的重量 II​

link:最后一块石头的重量 II 参考代码如下：

class Solution 
{
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        sort(stones.begin(),stones.end());
        int sum=0;
        for(int i:stones)
        {
            sum+=i;
        }
        if(sum==0)
        {
            return 0;
        }
        int bag=sum/2;
        vector<int> dp(bag+1,0);
        for(int i=0;i<stones.size();i++)
        {
            for(int j=bag;j>=stones[i];j--)
            {
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[bag]-dp[bag];
    }
};

这个题目看起来和背包问题不相关，实际上本题其实是尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的。 一堆的石头重量是sum，那么我们就尽可能拼成 重量为 sum / 2 的石头堆。 这样剩下的石头堆也是 尽可能接近 sum/2 的重量。 那么此时问题就是有一堆石头，每个石头都有自己的重量，是否可以 装满 最大重量为 sum / 2的背包。 背包出来后，这个题就好做了。

2.2.3 一和零​

link:一和零 参考代码如下：

class Solution 
{
public:
    int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int len=strs.size();
        vector<pair<int,int>> one_zero(len,{0,0});
        for(int i=0;i<len;i++)
        {
            for(char j:strs[i])
            {
                if(j=='0')
                {
                    one_zero[i].first++;
                }
                else
                {
                    one_zero[i].second++;
                }
            }
        }
        vector<vector<int>> dp(m+1,vector<int> (n+1,0));
        for(int i=0;i<len;i++)
        {
            for(int p=m;p>=one_zero[i].first;p--)
            {
                for(int q=n;q>=one_zero[i].second;q--)
                {
                    dp[p][q]=max(dp[p][q],dp[p-one_zero[i].first][q-one_zero[i].second]+1);
                }
            }
        }
        return dp[m][n];
    }
};

这个题比常规的01背包要麻烦一点，因为它相当于多了一维，正常的01背包是考虑背包大小和东西大小，这个题则是相当于把东西大小变成了0和1的个数这两个量，相当于在正常的背包问题上多了一次循环，其他的与正常01背包是一样的。

2.2.4 携带研究材料​

link:携带研究材料 参考代码如下：

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int main()
{
    int n,v;
    cin>>n>>v;
    vector<pair<int,int>> things(n);
    for(int i=0;i<n;i++)
    {
        cin>>things[i].first>>things[i].second;
    }
    vector<int> dp(v+1,0);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=v;j++)
        {
            if(j>=things[i].first)
            {
                dp[j]=max(dp[j],dp[j-things[i].first]+things[i].second);
            }
        }
    }
    cout<<dp[v]<<endl;
    return 0;
}

01背包做多了，来换个口味。这个题是一道完全背包问题。完全背包和01背包最大的区别在于可以拿的数量，01背包只有两种可能，拿或者不拿，因此在程序里一般使用倒着的遍历。而完全背包对于拿东西则没有限制，故而一般是正着遍历。

2.2.5 零钱兑换 II​

link:零钱兑换 II 参考代码入下：

class Solution 
{
public:
    int change(int amount, vector<int>& coins) 
    {
        int n=coins.size();
        sort(coins.begin(),coins.end());
        vector<unsigned long long> dp(amount+1,0);
        dp[0]=1;
        for(int i:coins)
        {
            for(int j=i;j<=amount;j++)
            {
                dp[j]+=dp[j-i];
            }
        }
        return dp[amount];
    }
};

定义 dp[j]：表示凑成金额 j 的组合数。 初始化：dp[0] = 1。意思是凑成金额 0 有一种方法（即什么都不选）。其他初始化为 0。 遍历顺序： 外层循环遍历硬币（物品）。 内层循环遍历金额（背包容量），从 coins[i] 到 amount。 关键点：必须先遍历硬币，再遍历金额。这样可以保证对于每种金额，硬币的使用顺序是固定的（例如先只用1，再考虑加入2），从而避免重复计算排列数（如 1+2 和 2+1 被视为同一种组合）