动态规划（数据结构笔试、复测、Leecode、牛客）_给定一个长度为 n 的数组,数组中的数为整数。 请你选择一个非空连续子数组,

基础介绍

简单

跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

递归

class Solution {
public:
    int jumpFloor(int number) {
        if(number <= 1)
            return 1;
        return jumpFloor(number-1)+jumpFloor(number-2);
        //看做是从第n个台阶下台阶，f(n)
        //有两种可能, 一个走一步，一个走两步，f(n) = f(n-1)+f(n-2);
        //初始条件 f(0)=0, f(1)=1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

动态规划

    int jumpFloor(int  number){
        vector<int> dp(number+1,0);
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <=number; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[number];
        //根据f[n] = f[n-1]+f[n-2];
    }
1
2
3
4
5
6
7
8
9
10

连续子数组最大和

给定一个长度为 n 的数组，数组中的数为整数。
请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。

	输入：8
		1 -2 3 10 -4 7 2 -5
	输出：18
	说明：
	经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18       
1
2
3
4
5

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    //输入
    int n;
    cin>>n;
    vector<int> val(n+1, 0);
    for(int i=0; i<n; i++)
    {
        int t = 0;
        cin>>t;
        val[i] = t;
    }
    
    //第i个数结尾的子数组最大连续和
    //dp[i] = max(dp[i-1]+val[i], val[i])
    vector<int> dp(n+1, 0);
    dp[0] = val[0];
    int res = dp[0];
    for(int i=1; i<n; i++){
        dp[i] = max(dp[i-1] + val[i], val[i]);
        res = max(res, dp[i]);
    }
    
    cout<<res<<endl;
    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

[NOIP2001]装箱问题

问题描述

有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
1
2
3

输入描述：

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
1
2
3

输出描述：

1个整数，表示箱子剩余空间
1

#include <bits/stdc++.h>
using namespace std;

//求背包的剩余空间最小=若干个物品的体积之和最大
//dp[i]:表示的是体积不超过i的放置方案的体积
//最小的剩余空间 = V-dp[v]
//
int main(){
    //输入
    int v, n;//v--体积，n--个数
    cin>>v>>n;
    vector<int> ths(n+1,0);
    for(int i=0; i<n; i++)
        cin>>ths[i];
    vector<int> dp(20001);

    
    
    for(int i=0; i<n; i++){
        for(int j=v; j>=ths[i]; j--) //因为容量必须大于当前所放物品
            dp[j] = max(dp[j], dp[j-ths[i]]+ths[i]);//选还是不选，在有容量的同时保证放入最多
            //dp[j] = min(dp[j], dp[j-ths[i]]);
        }
    cout<<v-dp[v]<<endl; 
    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

完全背包

描述

你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为v_i ,价值为w_i。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
1
2
3
4

每种物品有任意多个

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N];//f[j]表示在体积j下的总价值

int main(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>v[i]>>w[i];
    
    memset(f, -0x3f, sizeof(f));
    
    //在可以加入多个相同物品时，使用正向
    f[0] = 0;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=m-v[i]; j++){
            if(f[j] >= 0)
                f[j+v[i]] = max(f[j+v[i]], f[j]+w[i]);
        }
    }
    
    int res1 = 0, res2 = 0;
    for(int i=0; i<=m; i++)
        res1 = max(res1, f[i]);
    cout<<res1<<endl;
    
    if(f[m] < 0)
        res2 = 0;
    else
        res2 = f[m];
    cout<<res2<<endl;
    
    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

买卖股票的最好时机(一)

描述

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费
1
2
3
4

解题：

买卖股票有约束，根据题目意思，有以下两个约束条件：
条件 1：你不能在买入股票前卖出股票；
条件 2：最多只允许完成一笔交易。

因此 当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把 是否持股 设计到状态数组中
1
2
3
4
5

状态定义：
dp[i][j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数。
j = 0，表示当前不持股；
j = 1，表示当前持股。
注意：这个状态具有前缀性质，下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息，因此最后输出 dp[len - 1][0]

不持股时：

• 昨天不持股，今天什么都不干
• 昨天持股，今天卖出股票

持股时：

• 昨天持股，今天什么都不干
• 昨天不持股，今天买入

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        //低了买，高了卖
        //找相差最大的一对
        //贪婪算法，运行时间超出
        //int res=0;
     //for(int i=1; i<prices.size(); i++){
     //    for(int j=0; j<i; j++){
     //        if(prices[j] < prices[i]){
     //            res = max(res, prices[i]-prices[j]);
     //        }
     //    }
     //}
     //return res;
        
        //动态规划
        int len = prices.size();
        if(len < 2)
            return 0;
        vector<vector<int>> dp(len+1, vector<int>(2,0));
        
        dp[0][0] = 0;//初始化：不持股为0，持股就需要减去第一天（下标为0）的股价
        dp[0][1] = -prices[0];//持股，手上的现金数
        
        for(int i=1; i<len; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }
        return dp[len-1][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

中等

三角形最小路径和

给定一个正三角形数组，自顶到底分别有 1，2，3，4，5...，n 个元素，找出自顶向下的最小路径和。

每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点。
1
2
3

//从下到上
    int minTrace(vector<vector<int> >& triangle) {
        int n = triangle.size();
        vector<int> dp(n+1, 0);
        for(int i=n-1; i>=0; i--){
            for(int j=0; j<=i; j++){
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
            }       
        }
        return dp[0];  
    }
1
2
3
4
5
6
7
8
9
10
11

//从上到下
    int minTrace1(vector<vector<int> >& triangle) {
        // write code here
        int n = triangle.size();
        
        vector<vector<int>> dp(n, vector<int>(n,0));
        dp[0][0] = triangle[0][0];
        
        for(int i=1; i<n; i++){
            for(int j=0; j<=i; j++){
                if(j == 0)
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                else if(j == i)
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                else
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
        int res = INT_MAX;
        for(int i = 0; i<n ; i++)
            res = min(res, dp[n-1][i]);
        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

最长上升子序列(一)

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
1

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

#include <bits/stdc++.h>
using namespace std;

int main(){
    //输入
    int n;
    cin>>n;
    vector<int> val(n+1, 0);
    for(int i=0; i<n; i++)
        cin>>val[i];
    
    //dp数组保存每个数做结尾时对应的最大长度
    //条件：val[i]<val[j], dp[i]大于在j之前所有的dp中最大
    vector<int> dp(n+1, 1);
    
    for(int i=1; i<n ; i++){
        int mx = 0;
        for(int j=0; j<i; j++){
            if(val[j] < val[i])
                mx = max(mx, dp[j]);
        }
        dp[i] = mx+1;
    }
    
    int res = dp[0];
    for(int i=1; i<dp.size(); i++)
        res = max(res, dp[i]);
    cout<<res<<endl;
    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

最长公共子序列(一)

给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。
1

所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 “arcaea” 的子序列有 “ara” 、 “rcaa” 等。但 “car” 、 “aaae” 则不是它的子序列。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin>>n>>m;
    string s1, s2;
    cin>>s1>>s2;
    
    int dp[1001][1001] = {0};
    
    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][j+1], dp[i+1][j]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最长上升子序列(三)

描述

给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）
1

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        int n = arr.size();
        vector<int> tail(n);//希望末尾的数字越小越好
        vector<int> dp(n);//第i个元素的最大递增子序列长度
        int ans = 0;
        for(int i=0; i<n; i++){
            int left=0, right=ans;
            while(left<right){
                int mid = (left+right)/2;
                if(tail[mid] >= arr[i])
                    right = mid;
                else
                    left = mid+1;
            }
            tail[left] = arr[i];
            dp[i] = left+1;
            if(left == ans)
                ans++;
        }
        vector<int> res(ans);
        for(int i=n-1, j=ans; i>=0; i--){
            if(dp[i] == j)
                res[--j] = arr[i];
        }
        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
27
28
29
30
31
32
33
34
35
36

[模板] 背包

描述

	你有一个背包，最多能容纳的体积是V。
	现在有n个物品，第i个物品的体积为v_i,价值为w_i

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
1
2
3
4
5

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int main(){
    //输入
    int n, m;
    cin>>n>>m;
    int v[N], w[N];
    for(int i=1; i<=n; i++)
        cin>>v[i]>>w[i];
    
    int f[N];//f[j]表示体积为j的情况下的总价值
    memset(f, -0x3f, sizeof(f));
    
    f[0] = 0;//最开始体积为0价值为0
    for(int i=1; i<=n; i++){
        for(int j=m; j>=v[i]; j--){
            f[j] = max(f[j], f[j-v[i]]+w[i]);
        }
    }
    int res1=0, res2 = 0;
    for(int i=0; i<=m; i++)
        res1 = max(res1, f[i]);
    cout<<res1<<endl;
    
    if(f[m]<0)
        res2 = 0;
    else
        res2 = f[m];
    cout<<res2<<endl;
    
    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