devbox
代码独立开发者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划模板

作者：代码独立开发者 | 2024-01-31 14:39:29

赞

踩

动态规划模板

动态规划模板总结

动态规划适合求解的题目类型：
某一问题有很多重叠子问题。动态规划的每一个状态是由上一个状态推导出来的。
求解动态规划问题的步骤：

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组的初始化
  4. 确定遍历顺序

举例推导dp数组，打印出来看是否符合预期

经典案例：

  • 斐波拉契数列
    分析
    1.确定dp数组以及下标的含义
    dp[i]的定义为：第i个数的斐波那契数值是dp[i]
    2.确定递推公式
    状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
    3.dp数组如何初始化
    4.确定遍历顺序
    从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的。

连续子数组的最大和

状态转移方程：dp[i]=max(dp[i-1]+a[i],a[i])

#include<iostream>
#include<algorithm>

using namespace std;

/*
dp[i]=max(dp[i-1]+a[i],a[i])
其中，前面部分代表选择前面的区间的最大值，
后面部分代表直接选择a[i]。
*/

const int N = 2e5+1;
long long dp[N];
int main()
{
	int n;
	long long arr[N];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	} 
	dp[0] = arr[0];
	long long res = -1e9;
	for(int i=0;i<n;i++){
		dp[i] = max(dp[i-1]+arr[i],arr[i]);
		res = max(res,dp[i]);
	}
	cout<<res;
	return 0;
}
 

  • 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

最长上升子序列

状态转移方程：dp[i]=max(dp[i],dp[j]+1)

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1001;
int n;
int arr[N];
int dp[N];
int main(){
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>arr[i];
	}
	int res=0;
	for(int i=0;i<n;i++){
		dp[i]=1;//初始化 
		for(int j=0;j<=i;j++){
			if(arr[i]>arr[j]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		res = max(dp[i],res);
	}
	cout<<res; 
	return 0;
} 

  • 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

最长公共子序列（二维dp）

参考解析，详细过程
题目：

给定两个字符串 s1 和 s2，长度为 n 和 m 。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 “arcaea” 的子序列有 “ara” 、 “rcaa” 等。但 “car” 、 “aaae” 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。
数据范围 : 1≤m,n≤10001\leq m,n\leq 10001≤m,n≤1000 。保证字符串中的字符只有小写字母。
要求：空间复杂度 O(mn)O(mn)O(mn)，时间复杂度 O(mn)O(mn)O(mn)
进阶：空间复杂度 O(min(m,n))O(min(m,n))O(min(m,n))，时间复杂度 O(mn)O(mn)O(mn)

在这里插入图片描述
dp[i][j] 表示子序列 s1i 和 s2j的最长公共子序列的长度。

  • 当s1[i] == s2[j] 时候，找出s1[i-1],s2[j-1] 的最长公共子序列然后加上s1[i] 和s2[j]的最长公共子序列。（子序列不要求连续，子串才是连续的）
    即：
    dp[i+1][j+1] = dp[i][j] + 1

  • 当s1[i] != s2[j] 时，求s1[i-1] 和 s2[j] 与 s1[i] 和 s2[j-1] 的最长公共子序列
    即：
    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    最后,二维数组的最后一个元素就是答案

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1001;
int n,m;
char s1[N],s2[N] ;
int dp[N][N];
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s1[i];
	for(int i=0;i<m;i++) cin>>s2[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s1[i]==s2[j]){
				dp[i+1][j+1] = dp[i][j]+1;
			}else{
				dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

  • 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

最长公共子序列（输出序列）

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列

输入：
“1A2C3D4B56”,“B1D23A456A”
返回值：
“123456”

参考：

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        if(s1=="" || s2 =="") return "-1";
        int dp[s1.size()+1][s2.size()+1];
        //初始化
        for(int i=0;i<=s1.length();i++) dp[i][0] = 0;
        for(int j=0;j<=s2.length();j++) dp[0][j] = 0;
        //构造dp
        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        string res="";
        int i=s1.size(),j=s2.size();
        while(dp[i][j]>=1){
            if(s1[i-1]==s2[j-1]){
                res+=s1[i-1];
                i--;
                j--;
            }else if(dp[i-1][j]>=dp[i][j-1]) {
                i--;
            } else{
                j--;
            }
        }
            
        reverse(res.begin(),res.end());
        return res.empty() ? "-1" : res;
    }
};

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

最长公共子串

在这里插入图片描述

输入：

“1AB2345CD”,“12345EF”

返回值：

“2345”

解法1 动态规划：
状态转移方程：
dp[i][j] 表示str1以i结尾，str2以j结尾的字符串 的最长子串是为多少；
如果 str1[i]==str2[j]:
dp[i][j]=dp[i-1][j-1]+1
否则：
dp[i][j]=0

每次更新dp[i][j]后，更新最大值，并更新该子串结束位置。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int maxlen=0;//记录最长公共子串的长度
        int maxlastIndex = 0;//最长的子串最后一个字符的位置
        vector<vector<int> > dp(str1.length() + 1, vector<int>(str2.length() + 1, 0));   
        for(int i = 0; i <str1.length(); i++){
            for(int j = 0; j <str2.length(); j++){
                if(str1[i] == str2[j]){
                    dp[i+1][j+1] = dp[i][j]+1;
                    //更新最大值和长度
                    if(dp[i+1][j+1] > maxlen){
                        maxlen = dp[i+1][j+1];
                        maxlastIndex = i;
                    }
                    
                }else{
                    dp[i+1][j+1]=0;
                }
                
            }
        }
        return str1.substr(maxlastIndex-maxlen+1,maxlen);
    }
};

  • 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

解法2： 用滑动窗口
定义开始位置l和窗口长度i，以str1为准 ，在str2中滑动窗口，如果str1.find(窗口中的子串)，则更新子串。窗口i右移;否则开始位置l右移

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int l=0,i=1;//l是开始坐标，i是窗口的长度
        string res;
        while(l<str2.length() && l+i<=str2.length()){
            string temp(str2,l,i);//将str2以l开始的i个字符用于构造temp
            if(str1.find(temp)!=-1){
                i++;//如果在str1中找到了小窗内的子串，就把小窗增大
                res = temp;
            }else{
                l++;//如果找不到子串，就将窗口向右移动一格。
            }
        }
        return res;
    }
};

  • 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

编辑距离 （字符串增删改最少次数）

题目：

给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：
1.插入一个字符
2.删除一个字符
3.修改一个字符。
字符串长度满足 1≤n≤1000，保证字符串中只出现小写英文字母
在这里插入图片描述

dp[i][j]表示为从str1的第i位变化为str2的第j位次数

  • str1第i位和str2第j位一样 dp[i][j]=dp[i−1][j−1]
  • str1第i位和str2第j位不一样 dp[i][j]=min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1
 int editDistance(string str1, string str2) {
     // write code here
     int n1 = str1.length();
     int n2 = str2.length();
     int dp[1000][1000];//表示str1的前i个字符和str2的前j个字符的编辑距离
     //初始化边界
     for (int i = 0; i <= n1; i++) dp[i][0] = i;       
     for (int j = 0; j <= n2; j++) dp[0][j] = j;

     for (int i = 1; i <=n1; i++) {
         for (int j = 1; j <=n2; j++) {
             if (str1[i-1] == str2[j-1]) {
                 dp[i][j] = dp[i-1][j-1];
             } else {//选取最小的距离加上此处编辑距离1
                 dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
             }
         }
     }
     return dp[n1][n2];

 }

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

迷宫寻路（路径和最小）

给定一个包含非负整数的 M x N 迷宫，请找出一条从左上角到右下角的路径，使得路径上的数字总和最小。每次只能向下或者向右移动一步。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int minPath(vector<vector<int>> &grid,int m,int n){
    int dp[m][n];
    dp[0][0] = grid[0][0];
    //计算边
    for(int i=1;i<m;i++){
        dp[i][0] = dp[i-1][0]+grid[i][0];
    }
    for(int j=1;j<n;j++){
        dp[0][j] = dp[0][j-1]+grid[0][j];
    }
    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];
}
int main(){
    int m,n;
    cin>>m>>n;
    vector<vector<int>> grid;
    vector<int> v;
     int t;
    for(int i=0;i<m;i++){
        v.clear();
        for(int j=0;j<n;j++){
            cin>>t;
            v.push_back(t);
        }
        grid.push_back(v);
    }
    cout<<minPath(grid,m,n);
    return 0;
}

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39

01 背包问题模板

你有一个背包，最多能容纳的体积是V。
现在有n个物品，第i个物品的体积为vi​ ,价值为wi​。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数vi​和wi​，表示第i个物品的体积和价值。
在这里插入图片描述

输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

在这里插入图片描述
解题思路
第一问：

状态定义：dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。
状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即dp1[j]=Math.max(dp1[j−v[i]]+w[i],dp1[j]).

第二问：

状态定义：dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品。
.
状态初始化：将背包容量为0的情况设置价值为0，其它情况设置为最小的Integer型整数，表示不可达状态。后续所有的状态都需要从为0的状态转移过去。
.
状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即dp2[j]=Math.max(dp2[j−v[i]]+w[i],dp2[j]).

#include<bits/stdc++.h>
using namespace std;
int dp1[1001],dp2[1001];

int maxw(int v[],int w[],int n,int V){
    //dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。 
   for(int i=0;i<n;i++){
        for(int j=V;j>=v[i];j--){
            dp1[j] = max(dp1[j],dp1[j-v[i]]+w[i]);
        }
    }
    return dp1[V];
    
}
int maxv(int v[],int w[],int n,int V){
    //dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品。 
    memset(dp2, -0x3f, sizeof(dp2));
    dp2[0]=0;
    for(int i=0;i<n;i++){
        for(int j=V;j>=v[i];j--){
            dp2[j] = max(dp2[j],dp2[j-v[i]]+w[i]);
        }
    }
    if(dp2[V]<0) return 0;
    else return dp2[V];
}


int main(){
    int n,V;
    cin>>n>>V;
    int v[n],w[n];
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    int res1 = maxw(v,w,n,V);
    int res2 = maxv(v,w,n,V);
    cout<<res1<<endl<<res2;
    return 0;
}

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

完全背包问题模板

遍历体积 j 时从逆序改为顺序

你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为vi​ ,价值为wi.

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
在这里插入图片描述

0-1背包是完全背包的特殊情况!
刚好装满时最大价值与直接最大价值的区别在于base case初始化的不同！

(01背包中)，逆序是为了保证更新当前状态时，用到的状态是上一轮的状态，保证每个物品只有一次或零次;
在这里，因为每个物品可以取任意多次，所以不再强求用上一轮的状态，即本轮放过的物品，在后面还可以再放;

#include<bits/stdc++.h>
using namespace std;
int dp1[1001],dp2[1001];

int maxw(int v[],int w[],int n,int V){
    //dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。 
   for(int i=0;i<n;i++){
        for(int j=v[i];j<=V;j++){
            dp1[j] = max(dp1[j],dp1[j-v[i]]+w[i]);
        }
    }
    return dp1[V];
    
}
int maxv(int v[],int w[],int n,int V){
    //dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品。 
    //将所有状态置为最小的Integer型整数，表示不可达状态。
    //后续所有的状态都需要从为0的状态转移过去。
    memset(dp2, -0x3f, sizeof(dp2));
    dp2[0]=0;//容量为0的背包，恰好装满下的价值只能为0
    for(int i=0;i<n;i++){
        for(int j=v[i];j<=V;j++){
            dp2[j] = max(dp2[j],dp2[j-v[i]]+w[i]);
        }
    }
    if(dp2[V]<0) return 0;
    else return dp2[V];
}


int main(){
    int n,V;
    cin>>n>>V;
    int v[n],w[n];
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    int res1 = maxw(v,w,n,V);
    int res2 = maxv(v,w,n,V);
    cout<<res1<<endl<<res2;
    return 0;
}

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50826
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号