目录
1.斐波那契数列
这个题我们用动态规划
首先确定一般情况的状态：第i个斐波那契数
思考怎么确定状态方程：他的前一个数+前前数
初始化：F(0) = 1 ; F(1) = 1;
int Fibonacci(int n) {
int F[n + 1];
F[0] = 1;
F[1] = 1;
for (int i = 2; i < n; i++)
{
F[i] = F[i - 1] + F[i - 2];
}
return F[n - 1];
}2.跳台阶
这个就是斐波那契套个应用题的外壳
思路和上题几乎无差别
int jumpFloor(int number) {
int dp[number];
dp[0]=1;
dp[1]=2;
for(int i=2;i<number;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[number-1];
}3.最小花费爬楼梯
int minCostClimbingStairs(vector<int>& cost) {
// write code here
//状态：dp[i]:走到第i个台阶总共需要支付的费用
//状态方程：因为可以选择向上走一个，dp[i]=dp[i-1]+cost[i-1];
///或者两个台阶:dp[i]=dp[i-2]+cost[i-2];
//最小花费，就是两种情况的最小值
vector<int> dp(cost.size()+1);
dp[0]=0;dp[1]=0;
for(int i=2;i<=cost.size();i++)
{
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[cost.size()];
}4.把字符串转换成整数
最经典的代码，几乎没有难度
int StrToInt(string str) {
int flag=1;
int i=0;
if(str[i]=='-' || str[0]=='+')
{
if(str[0]=='-')
flag=-1;
i++;
}
int ans=0;
for(;i<str.size();i++)
{
if(str[i]<'0'||str[i]>'9')
return 0;
ans=ans*10+str[i]-'0';
}
return flag*ans;
}5. 最长公共子序列(二)
不是最长子串（必须连续）
这个题用最经典的动态规划做，首先我们要确定状态是什么？
两个字符串s1，s2
状态：s1遍历到下标为i，s2遍历到下标为j，此时的公共子序列
怎么确定状态方程？ 用一张表来记录状态时刻，最长公共子序列的长度
肯定当有一个下标为0时，最长公共子序列长度为0
那么其余部分怎么补充？
情形一：s1遍历到下标i，s2遍历到下标j，此时如果对应的字符相等，那么最长公共子序列长度=同时减去一个下标（相当于把相等字符减去之后的状态对应的长度）+1（这个1就是最长公共子序列加上这个相等字符，对应长度+1）
情形二：s1遍历到下标i，s2遍历到下标j，此时如果对应的字符不相等，那此时的序列长度=max（s1减一个下标，s2下标不变 对应的长度 及 s1下标不变，s2下标减1 对应的长度）
至此这张表制作完成
下面就是根据这个表（最长公共子序列的长度）反推最长公共子序列到底是什么
规定一下反向走的方向，如果碰到dp[x][y]==dp[x-1][y]那往左走（x--），如果dp[x][y]==dp[x][y-1]
那么往上走，如果都不是，那么直接把这个下标对应的s1/s2（反正字符相等）加到要返回的字符串
所以最后的代码
string LCS(string s1, string s2) {
// write code here
int n=s1.size();
int m=s2.size();
string ans;
int dp[n+1][m+1];
for(int j=0;j<=m;j++)
{
dp[0][j]=0;
}
for(int i=0;i<=n;i++)
{
dp[i][0]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
if(dp[n][m]==0) return "-1";
int x = n;
int y = m;
while (x != 0 && y!= 0) {
if (dp[x][y] == dp[x-1][y]) {
x--;
} else if (dp[x][y] == dp[x][y-1]) {
y--;
} else {
ans += s1[x-1];
x--;
y--;
}
}
reverse(ans.begin(), ans.end());
return ans;
}