【思特奇杯.云上蓝桥-算法训练营】第3周

【思特奇杯.云上蓝桥-算法训练营】第3周 1.斐波那契数

动态规划

class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        
        int [] dp=new int[n+1];
        dp[0]=0;dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

2.第 N 个泰波那契数

class Solution {
    public int tribonacci(int n) {
       if(n==0) return 0;
       if(n==1) return 1;
       if(n==2) return 1;
       int [] dp=new int[n+1];
       dp[0]=0;dp[1]=1; dp[2]=1;
       for(int i=3;i<=n;i++){
           dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
       }
        return dp[n];
    }
}

3. 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        int [] dp=new int[n+1]; 
        dp[1]=1;dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];

    }
}

4. 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n=cost.length;
        int[] dp=new int[n+1]; //表示爬到第i级台阶需要的最少花费
        dp[0]=0;dp[1]=0;

        for(int i=2;i<=n;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }

        return dp[n];
        
    }

}

5.买卖股票的最佳时机

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int [][]dp=new int [n+1][2]; //表示第i天持有状态( 1 表示持有，0 表示没有持有)是j,所能获得最大利润
        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;

        for(int i=1;i<=n;i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i-1]);
        }
        return dp[n][0];
    }
}

6.最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m=text1.length();
        int n=text2.length();
        int dp[][] =new int [m+1][n+1];
        // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
        // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
        // base case: dp[0][..] = dp[..][0] = 0
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
            if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=1+dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.max(
                    dp[i-1][j],dp[i][j-1]
                );
                }
           
    }
}