数组中两个字符串的最短距离
1.题目：数组中两个字符串的最小距离_牛客题霸_牛客网
给定一个字符串数组strs，再给定两个字符串str1和str2，返回在strs中str1和str2的最小距离，如果str1或str2为null，或不在strs中，返回-1。
2.算法思想：
1>暴力解法：利用两层for循环，第一层找str1的位置，当找到一个str1时，进入第二层循环找str2,并更新两者间的最短距离
2>优化解法：定义两个变量记录str1,str2的下标，再用一层for循环遍历数组中的字符串，若s==str1,到s的前面去找str2的位置，若前面有str2,则更新两者间的最短距离，再更新str1的位置信息；若s==str2,到s的前面去找st12的位置，若前面有str1，则更新两者间的最短距离，再更新str2的位置信息
3.代码实现
#include <iostream>
#include<string>
#include<climits>
using namespace std;int main() {int n;while(scanf("%d",&n)!=EOF){string str1,str2;cin>>str1>>str2;string s;int index1=-1,index2=-1;int ret=INT_MAX;for(int i=0;i<n;i++){cin>>s;if(s==str1)//去前面找离他最近的str2{if(index2!=-1){ret=min(ret,i-index2);}index1=i;//更新str1的下标}if(s==str2)//去前面找离他最近的str1{if(index1!=-1) {ret=min(ret,i-index1);}index2=i;//更新str2的下标}}//当str1或str2为空字符串时返回-1if(str1.size()==0 || str2.size()==0) ret=-1;//当str1或str2不存在与数组中时返回-1if(index1==-1 || index2==-1) ret=-1;cout<<ret<<endl;}
}最小花费爬楼梯（动态规划）
1.题目：最小花费爬楼梯_牛客题霸_牛客网
给定一个整数数组cost ，其中cost[i] 是从楼梯第i个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
2.算法思想：利用数组dp统计到第i阶楼梯的最小花费,最终dp[n]就是爬到顶部所需的最小的花费
dp[i]表示：到达i位置的最小花费
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
dp[0]=dp[1]=0;
3.代码实现
class Solution {
public:int minCostClimbingStairs(vector<int>& cost){int n=cost.size();vector<int> dp(n+1,0);for(int i=2;i<n+1;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
};