1.買賣股票的最佳時機
https://blog.csdn.net/qq_41277628/article/details/113322136
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。
1 #include <stdio.h>
2
3 #define N 6
4
5 int main()
6 {
7 int min,temp;
8 int a[] = {7,1,5,3,6,4};
9 min = a[0];
10 temp = 0;
11 for(int i = 0;i<N;i++)
12 {
13 if(a[i] < min)
14 {
15 min = a[i];
16 }
17 else if((a[i]-min)>temp)
18 {
19 temp = a[i] - min;
20 }
21 }
22 printf("最高收益為%d元\n",temp);
23
24 return 0;
25 }2.盛最多水的容器
給定一個長度為 n 的整數(shù)數(shù)組?height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲存的最大水量。
https://violentayang.blog.csdn.net/article/details/123061036
1 #include <stdio.h>
2 #include <string.h>
3
4 #define N 9
5
6 int main()
7 {
8 int a[N] = {1,8,6,2,5,4,8,3,7};
9 int i = 0,j = N-1,sun = 0,top = 0;
10 while(i<j)
11 {
12 if(a[i]<a[j])
13 {
14 sun = (j-i)*a[i];
15 if(sun>top)
16 {
17 top = sun;
18 }
19 i++;
20 }
21 else
22 {
23 sun = (j-i)*a[j];
24 if(sun>top)
25 {
26 top = sun;
27 }
28 j--;
29 }
30 }
31 printf("可以盛%d噸的水\n",top);
32
33 return 0;
34 }c++實現(xiàn)：
1 #include<iostream>
2 #include<vector>
3 using namespace std;
4
5 class node{
6 public:
7 int maxsrea(vector<int>& height){
8 int ans = 0;
9 int l = 0,r = height.size()-1;
10 while(l<r){
11 ans = max(ans,min(height[l],height[r]) * (r-l));
12 if(height[l] < height[r]) l++;
13 else r--;
14 }
15 return ans;
16 }
17 };
18
19 int main()
20 {
21 node n;
22 vector<int> height = {1,8,6,2,5,4,8,3,7};
23 cout << n.maxsrea(height) << endl;
24
25 return 0;
26 }3.不同路徑
一個機器人位于一個 m x n 網(wǎng)格的左上角 。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角。
問總共有多少條不同的路徑？
https://blog.csdn.net/C_chengxuyuan/article/details/119980859
1 #include <stdio.h>
2 #include <string.h>
3
4 int main()
5 {
6 int x,y;
7 int a[100][100];
8 printf("輸入網(wǎng)格的長和寬\n");
9 scanf("%d%d",&x,&y);
10
11 for(int i = 0;i<x;i++)
12 {
13 a[i][0] = 1;
14 }
15
16 for(int j = 0;j<y;j++)
17 {
18 a[0][j] = 1;
19 }
20
21 for(int i = 1;i<x;i++)
22 {
23 for(int j = 1;j<y;j++)
24 {
25 a[i][j] = a[i-1][j] + a[i][j-1];
26 }
27 }
28
29 printf("長和寬為%d,%d的網(wǎng)格，總共有%d條不同的路徑\n",x,y,a[x-1][y-1]);
30
31 return 0;
32 }c++實現(xiàn)：
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 class node{
6 public:
7 int uniquePath(int m,int n){
8 vector<vector<int>> f(m,vector<int>(n,1));
9 for(int i = 1;i<m;i++){
10 for(int j = 1;j<n;j++){
11 f[i][j] = f[i-1][j] + f[i][j-1];
12 }
13 }
14 return f[m-1][n-1];
15 }
16 };
17
18 int main()
19 {
20 int y = 3,x = 7;
21 node n;
22 cout << "長為7，寬為3的網(wǎng)格從左上角到右下角的路徑有：" << n.uniquePath(x,y);
23
24 return 0;
25 }?不同路徑中間有障礙物（力扣第63題）
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 class node{
6 public:
7 int unique(vector<vector<int>>& o){
8 int m = o.size(),n = o[0].size();
9 vector<vector<int>> f(m,vector<int>(n));
10 for(int i = 0;i<m;i++){
11 for(int j = 0;j<n;j++){
12 if(o[i][j] == 1) continue;
13 if(!i&&!j) f[i][j] = 1;
14 else{
15 if(i) f[i][j] += f[i-1][j];
16 if(j) f[i][j] += f[i][j-1];
17 }
18 }
19 }
20 return f[m-1][n-1];
21 }
22 };
23
24 int main()
25 {
26 node n;
27 vector<vector<int>> cur;
28 cur.push_back({0,0,0});
29 cur.push_back({0,1,0});
30 cur.push_back({0,0,0});
31 cout << n.unique(cur) << endl;
32
33 return 0;
34 }4.最小路徑和
一個機器人位于一個 m x n 網(wǎng)格的左上角 ，m x n的網(wǎng)格中分布著不同的數(shù)字
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角，找出路徑的最小和。
1 #include <stdio.h>
2 #include <string.h>
3
4 #define N 3
5 #define M 3
6
7 int main()
8 {
9 int a[N][M] = {{1,3,1},{1,5,1},{4,2,1}};
10 int b[100][100];
11
12 b[0][0] = a[0][0];
13
14 for(int i = 1;i<N;i++)
15 {
16 b[i][0] = b[i-1][0] + a[i][0];
17 }
18
19 for(int j = 1;j<M;j++)
20 {
21 b[0][j] = b[0][j-1] + a[0][j];
22 }
23
24 for(int i = 1;i<N;i++)
25 {
26 for(int j = 1;j<N;j++)
27 {
28 b[i][j] = (b[i-1][j] > b[i][j-1] ? b[i][j-1]:b[i-1][j])+a[i][j];
29 }
30 }
31
32 printf("長和寬為%d,%d的網(wǎng)格，最小路徑和為%d\n",N,M,b[N-1][M-1]);
33
34 return 0;
35 }5.最長上升子序列
一個數(shù)的序列bi，當b1 < b2 < ... < bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1,a2,...,aN)，我們可以得到一些上升的子序列(ai1,ai2,...,aiK)，
這里1≤i1 < i2 < ... < iK≤N。比如，對于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4，比如子序列(1,3,5,8)。文章來源：http://www.zghlxwxcb.cn/news/detail-722934.html
你的任務(wù)，就是對于給定的序列，求出最長上升子序列的長度。文章來源地址http://www.zghlxwxcb.cn/news/detail-722934.html
1 #include <stdio.h>
2 #include <string.h>
3
4 #define N 7
5
6 int main()
7 {
8 int max = 0;
9 int a[N],dp[N];
10 printf("輸入一個數(shù)組\n");
11 for(int i = 1;i<=N;i++)
12 {
13 scanf("%d",&a[i]);
14 }
15
16 for(int i = 0;i<N;i++)
17 {
18 dp[i] = 1;
19 }
20
21 for(int i = 1;i<=N;i++)
22 {
23 for(int j = i-1;j>0;j--)
24 {
25 if(a[i]>a[j]&&dp[j]>=dp[i])
26 {
27 dp[i] = dp[j]+1;
28 if(dp[i]>max)
29 {
30 max = dp[i];
31 }
32 }
33 }
34 }
35 printf("最長上升子序列的長度為%d\n",max);
36
37 return 0;
38 }6.最接近的三數(shù)之和（力扣16題）
1 #include <iostream>
2 #include <vector>
3 #include<algorithm>
4 using namespace std;
5
6 class node{
7 public:
8 int threesun(vector<int>& nums,int target){
9 int ans = nums[0] + nums[1] + nums[2];
10 sort(nums.begin(),nums.end());
11 for(int i = 0;i<nums.size();i++){
12 int l = i + 1,r = nums.size() - 1;
13 while(l<r){
14 int sum = nums[i] + nums[l] + nums[r];
15 if(sum == target) return sum;
16 if(abs(sum-target) < abs(ans-target)) ans = sum;
17 if(sum < target) l++;
18 else r--;
19 }
20 }
21 return ans;
22 }
23 };
24
25 int main()
26 {
27 node n;
28 vector<int> cur = {-1,2,1,-4};
29 cout << n.threesun(cur,1) << endl;
30
31 return 0;
32 }到了這里，關(guān)于C/C++ 動態(tài)規(guī)劃面試算法題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
