走迷宫

844. 走迷宫 - AcWing题库

考点:BFS

超时的代码：DFS

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =110;
int map[N][N];
int f[N][N];
int n,m;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};// 上下左右
int MinLenth=0x3f;
int curMin;
void dfs(int x,int y){
    if(curMin>MinLenth) return;
    if(x==n&&y==m){
        MinLenth=min(MinLenth,curMin);
    }
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a>=1 && a<=n && b<=m){
             if(f[a][b]==1) continue;
             curMin++;
             dfs(a,b);
             curMin--;
        }
    }
}
int main(void){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>map[i][j];
        }
    }
    memset(f,-1,sizeof(f));
    dfs(1,1);
    cout<<MinLenth<<endl;
    return 0;
}

参照抽风大佬的DFS

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
44
45
46
47
48
49
50
51
52
#include <cstring>
#include <iostream>
using namespace std;

int a[110][110], dist[110][110];
int Next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int Min = 99999999;
int p, q, n, m;

void dfs(int x, int y)
{
    //reach the destination
    if(x == p && y == q) return ;

    int i, tx, ty;   
    for(i = 0; i <= 3; i++)
    {
        tx = x + Next[i][0];
        ty = y + Next[i][1];

        if(tx < 1 || tx > n || ty < 1 || ty > m)
            continue;

        if(!a[tx][ty] && dist[tx][ty] > dist[x][y] + 1)
        {
            dist[tx][ty] = dist[x][y] + 1;
            dfs(tx, ty);
        }
    }

    return;
}

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];

    //the position of destination
    p = n, q = m;

    memset(dist, 0x3f, sizeof dist);
    dist[1][1] = 0;
    dfs(1, 1);

    cout << dist[n][m] << endl;

    return 0;
}

这个代码中 dist[][]中装的就是起始点到当前点的最小路径，每次

dist[tx][ty] > dist[x][y] + 1的时候更新，说明如果本次走到tx，ty的距离小于曾经的距离就更新，每次更新过后一定都是dist[][]当前的最小值

BFS做法（使用队列）

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
44
45
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
//#include <utility>
using namespace std;
const int N = 110;
int d[N][N];
int g[N][N];
int m, n;
queue<pair<int, int>>q;
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int bfs() {
    q.push({ 1, 1 });
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        d[1][1]=0; //初始化要记住
        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i];
            int y = t.second + dy[i];
            if (x >= 1 && x <= n && y >= 1 && y <= m && d[x][y] == -1 && g[x][y] == 0) {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({ x,y });
            }
        }
    }
    return d[n][m];


}

int main(void) {

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    memset(d, -1, sizeof(d));
    cout << bfs() << endl;

    return 0;
}

推箱子（困难）

做好心理准备…

2023.6.10过了一天了，还是没学会…

需要满足的条件

  1. 箱子移动的次数最少：使用BFS来对箱子求到终点的最短距离
  2. 人移动的次数最少
  3. 移动箱子的操作序列的字典序最小：按照上下左右顺序即可
  4. 移动人的操作序列的字典序最小

​

1的解决:

​ 箱子的位置当作一个状态的话，并不知道箱子是从哪个方向推过来的(上下左右四个方向),所以要记录箱子从哪个方向推过来的。（x,y,dir）dir代表方向

2的解决:

​ 人的移动总次数最少:对人进行BFS到箱子的之前可能存在的位置

image-20230610214912059

买卖股票最佳时机 1

买卖股票的最佳时机

属性是最大利润

这个里面dp[i][0]的意思是持有股票，dp[i][1]的意思是不持有股票最大利润

注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态

动态规划做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
    const int N =100010;
    int dp[N][2]; // dp数组肯定是利润
    //memset(dp,0,sizeof (dp)); //初始化为0
    dp[0][0]=-prices[0];
    dp[0][1]=0;
    for(int i=1;i<prices.size();i++){
         dp[i][0]=max(dp[i-1][0],-prices[i]); // 持有股票，利润肯定是0
         dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]); //i天卖出股票，前一天保持持有
    }
       return dp[prices.size()-1][1];
    }
};

贪心做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices) {
      const int N =100010;
      int dp[N][2];
      int n=prices.size();
      if(n==1) return 0;
      dp[0][0]= -prices[0];
      dp[0][1]= 0;
      int res=0;
      for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][0],-prices[i]);
        dp[i][1]=prices[i]+dp[i][0];
        res=max(dp[i][1],res);
      }
      return res;
    }
};

买卖股票最佳时机 2

买卖股票最佳时机 2

动态规划的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
       const int N =100010;
       int n=prices.size();
       if(n==1) return 0;
       int dp[N][2];
       dp[0][0]=-prices[0];
       dp[0][1]=0;
       for(int i=1;i<n;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]+dp[i-1][0]);
       } 
       return dp[n-1][1];
    }
};

贪心的做法

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
};

买卖股票最佳时机 3

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

开始上难度了捏

这个是个多状态的问题，直接看注释把

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
/* 
 dp 数组的值表示当前的最大利润

 第一次持有:   dp[i][1]=max(dp[i-1][1],-price[i]);   第一次持有，当前的利润肯定是0-price[i]
 第一次不持有: dp[i][2]=max(dp[i-1][1],dp[i-1][1]+price[i]);
 第二次持有:   dp[i][3]=max(dp[i-1][3],dp[i-1][2]-price[i]);  第一次不持有的条件下，再次持有
 第二次不持有: dp[i][4]=max(dp[i-1][4],dp[i-1][3]+price[i]);
 初始化:
       dp[0][1]=-price[0];
       dp[0][2]=0;
       dp[0][3]=-price[1];  
       dp[0][4]=0;

*/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
     int n= prices.size();
     const int N =100010;
     int dp[N][5];
       dp[0][1]=-prices[0];
       dp[0][2]=0;
       dp[0][3]=-prices[0];  
       dp[0][4]=0;
     if(n==1) return 0;
     for(int i=1;i<n;i++){
     dp[i][1]=max(dp[i-1][1],-prices[i]);  // 第一次持有，当前的利润肯定是0-price[i]
     dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);
     dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]); // 第一次不持有的条件下，再次持有
     dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);


     }
     return dp[n-1][4]; // 第二次卖出是最大值  

    }
};

买卖股票的最佳时机4

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

本题目应该与上文受到上文的启发，本题目是k次，要有2*k个状态，则需要内嵌一个2*k的for循环即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        const int N =2000;
        int dp[N][300];
        int n=prices.size();
        memset(dp,0,sizeof(dp));
        for(int j=0;j<=2*k;j++){
           if(j%2)
           dp[0][j]=-prices[0];
           else 
           dp[0][j]=0;
        }
        for(int i=1;i<n;i++){
           for(int j=1;j<=2*k;j++){
                if(j%2)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
                else 
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
           }
        }
        return dp[n-1][2*k];
    }
};

买卖股票的最佳时机5 含冷冻期

最长公共子数组

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）

由于是最长公共子数组，要求是连续的，所以递推公式满足A[i-1]和B[i-1]相等就行。

如果定义dp[i][j]的含义是下标i为结尾的A，和以下标j为结尾的B，最长重复子数组长度为dp[i][j]，如果定义 dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，那么 第一行和第一列毕竟要进行初始化，如果A[i] 与 B[0] 相同的话，对应的 dp[i][0]就要初始为1，

即dp[i][j]=dp[i-1][j-1]+1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
       const int N =1010;
       int dp[N][N]; // 如何表示状态,dp[i][j]以i-1,j-1为结尾的元素最长公共子数组的长度
       memset(dp,0,sizeof(dp));
       for(int i=1;i<=nums1.size();i++){
          for(int j=1;j<=nums2.size();j++){
              if(nums1[i-1]==nums2[j-1]){
                  dp[i][j]=dp[i-1][j-1]+1; // 这个就是递推公式，本题目结束了
              } 
          }
       }
       int res=0;
       for(int i=0;i<=nums1.size();i++){
           for(int j=0;j<=nums2.size();j++){
               res=max(res,dp[i][j]);
           }
       }
    return res;
    }
};

最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

先来看贪心算法:使用分治法求最大子序列之和 - stonesola - 博客园 (cnblogs.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
       int nsum=0;
       int n=nums.size();
       int res=-100000;
       for(int i=0;i<n;i++){
           if(nsum>0){
             nsum+=nums[i];
           }
           else {
             nsum=nums[i];
           }
           res=max(nsum,res);
       }
       return res;
    }
};