题解 | #动态规划专题#

斐波那契数列

class Solution {
public:
    int Fibonacci(int n) {
        int a=1,b=1,c=1;
        for(int i=3;i<=n;i++) {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};

跳台阶

class Solution {
public:
    int jumpFloor(int number) {
        if(number==1) return 1;
        if(number==2) return 2;
        int a=1,b=2,c=0;
        for(int i=3;i<=number;i++) {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};

最小花费爬楼梯

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

最长公共子序列

class Solution {
public:
    string LCS(string s1, string s2) {
        if(s1.empty() || s2.empty()) return "-1";
        int dp[s1.size()+1][s2.size()+1];
        for(int i = 0; i <= s1.size(); i++)
            dp[i][0] = 0;
        for(int j = 0; j <= s2.size(); j++)
            dp[0][j] = 0;
        for(int i = 1; i <= s1.size(); i++) {
            for(int j = 1; j <= s2.size(); j++)
                dp[i][j] = (s1[i-1] == s2[j-1]) ? dp[i-1][j-1] + 1: max(dp[i-1][j], dp[i][j-1]);
        }
        string res = "";
        for(int i = s1.size(), j = s2.size(); dp[i][j] >= 1;) {
            if(s1[i-1] == s2[j-1]) {
                res += s1[i-1];
                i--;j--;
            }
            else if(dp[i-1][j] >= dp[i][j-1]) i--;
            else j--;
        }
        reverse(res.begin(), res.end());
        return res.empty() ? "-1" : res;
    }
};