目录

最⼩花费爬楼梯（动态规划-线性dp）

题目解析

讲解算法原理

编写代码

数组中两个字符串的最⼩距离（模拟+贪⼼）

题目解析

讲解算法原理

编写代码

---

最⼩花费爬楼梯（动态规划-线性dp）

题目解析

1.题目链接：最小花费爬楼梯_牛客题霸_牛客网

2.题目描述

描述

给定一个整数数组 cost \cost  ，其中 cost[i]\cost[i]  是从楼梯第i \i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 1 \le n \le 10^5 \1≤n≤105  ，数组中的值满足 1 \le cost_i \le 10^4 \1≤costi​≤104 

输入描述：

第一行输入一个正整数 n ，表示数组 cost 的长度。

第二行输入 n 个正整数，表示数组 cost 的值。

输出描述：

输出最低花费

示例1

输入：

3
2 5 20

输出：

5

说明：

你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5 

示例2

输入：

10
1 100 1 1 1 90 1 1 80 1

输出：

6

说明：

你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。     

讲解算法原理

解法：
算法思路：
简单线性dp。

编写代码

c++算法代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int cost[N];
int dp[N];
int main()
{cin >> n;for(int i = 0; i < n; i++) cin >> cost[i];for(int i = 2; i <= n; i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}cout << dp[n] << endl;return 0;
}

java算法代码：

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] cost = new int[n];int[] dp = new int[n + 1];for(int i = 0; i < n; i++){cost[i] = in.nextInt();}for(int i = 2; i <= n; i++){dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}System.out.println(dp[n]);}
}

 

数组中两个字符串的最⼩距离（模拟+贪⼼）

题目解析

1.题目链接：数组中两个字符串的最小距离__牛客网

2.题目描述

 

输入描述:

输入包含有多行，第一输入一个整数n（1≤n≤105）（1 \leq n \leq 10^5）（1≤n≤105），代表数组strs的长度，第二行有两个字符串分别代表str1和str2，接下来n行，每行一个字符串，代表数组strs (保证题目中出现的所有字符串长度均小于等于10)。

输出描述:

输出一行，包含一个整数，代表返回的值。

示例1

输入

1
CD AB
CD

输出

-1

示例2

输入

5
QWER 666
QWER
1234
qwe
666
QWER

输出

1

讲解算法原理

解法：
算法思路：
⼩贪⼼，或者是⼩dp：
◦ ⽤ prev1 标记 i 位置之前最近⼀次出现的第⼀个字符串的下标；◦ ⽤ prev2 标记 i 位置之前最近⼀次出现的第⼆个字符串的下标。

编写代码

c++算法代码：

#include <iostream>
#include <string>
using namespace std;
int main()
{int n;string s1, s2;string s;cin >> n;cin >> s1 >> s2;int prev1 = -1, prev2 = -1, ret = 0x3f3f3f3f;for(int i = 0; i < n; i++){cin >> s;if(s == s1) // 去前⾯找最近的 s2 {if(prev2 != -1){ret = min(ret, i - prev2);}prev1 = i;}else if(s == s2) // 去前⾯找 s1{if(prev1 != -1){ret = min(ret, i - prev1);}prev2 = i;}}if(ret == 0x3f3f3f3f) cout << -1 << endl;else cout << ret << endl;return 0;
}

java算法代码：

import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) throws Throwable{BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));int n = Integer.parseInt(reader.readLine());String[] str = reader.readLine().split(" ");String s1 = str[0], s2 = str[1];int prev1 = -1, prev2 = -1, ret = 0x3f3f3f3f;for(int i = 0; i < n; i++){String s = reader.readLine();if(s.equals(s1)) // 去前⾯找最近的 s2{if(prev2 != -1){ret = Math.min(ret, i - prev2);}prev1 = i;}else if(s.equals(s2)) // 去前⾯找最近的 s1 {if(prev1 != -1){ret = Math.min(ret, i - prev1);}prev2 = i;}}System.out.println(ret == 0x3f3f3f3f ? -1 : ret);}
}