【思特奇杯.云上蓝桥-算法训练营】第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] = 0for(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]);}}
}