算法康复训练03

1.知识点总结

题目	知识点	难度
二叉树遍历（前序，中序，后序）	二叉树	🐸
斐波那契	DP	🐸
跳台阶	DP	🐸
最小耗费爬楼梯	DP	🐸
最长公共子序列	DP	🐸🐸

2. 分题题解

2.1 二叉树遍历

这种难度算作中档是不是……代码就不列了，这个不兴WA

2.2 斐波那契

emm……基础中的基础，但是需要提醒，在数据量较大的时候可以用矩阵快速幂

2.3 跳台阶

还是属于基础题

2.4 最小花费爬楼梯

这个还是基础题，不涉及到多种状态,放上题解叭，不然过于空旷了

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        // write code here
        int hight=cost.size();//楼层高度
        vector<int>dp(hight+1);
        fill(dp.begin(),dp.end(),0);
        //初始化
        dp[0]=cost[0];dp[1]=cost[1];
        for(int i=2;i<hight+1;i++){
            dp[i]=min(dp[i-1],dp[i-2]);
            if(i<hight){
                dp[i]+=cost[i];
            }
        }
        return dp[hight];
    }
};

2.5 最长公共子序列

emm，最长公共自序列的倒推，个人觉得还是蛮有难度的，起码第一次做的话，不是很好下手

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int len1=s1.length();
        int len2=s2.length();
        string ans="";//还需要记录下来最长公共子序列
        int dp[2001][2001];
        fill(dp[0],dp[0]+2001*2001,0);
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(s1[i]==s2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    if(dp[i][j+1]>dp[i+1][j]){
                        dp[i+1][j+1]=dp[i][j+1];
                    }else{
                        dp[i+1][j+1]=dp[i+1][j];
                    }
                }
            }
        }
       
        if(dp[len1][len2]!=0){
            //反推结果
            int i=len1;int j=len2;
            while(i>0&&j>0){
                if(s1[i-1]==s2[j-1]){
                    ans+=s1[i-1];
                    i--;
                    j--;
                }else{
                    if(dp[i-1][j]<dp[i][j-1]){
                        j--;
                    }else if(dp[i-1][j]>dp[i][j-1]){
                        i--;
                    }else{//这边其实有两个分支可以走，任选一个就好
                        j--;
                    }
                }
            }
            reverse(ans.begin(),ans.end());
            return ans;
        }else{
            return "-1";
        }
    }
};

3. 参考资料