目录
题一：斐波那契数列
递归方法是2的n次方的时间复杂度。
递归代码：
package DynaticPractice;
public class Problem1 {
public static void main(String[] args) {
System.out.println(fib(5));
}
public static int fib(int n){
if(n==0) return 0;
if(n==1) return 1;
return fib(n-1)+fib(n-2);
}
}带有缓存的递归，会使时间复杂度得到大幅度优化。
时间复杂度为O(n)。
缓存即记录中间值
/**
* 带有缓存的解法 * 时间复杂度为O(n)
*/
public static int fib2(int n){
int[] dp=new int[n+1];
Arrays.fill(dp,-1);
return f2(n,dp);
}
public static int f2(int i,int[] dp){
if(i==0){
return 0;
}
if(i==1){
return 1;
}
if(dp[i]!=-1){
return dp[i];
}
int ans=f2(i-1,dp)+f2(i-2,dp);
dp[i]=ans;
return ans;
}优化的方法：
/**
* 从底到顶计算的方法
*/
public static int fib3(int n){
if(n==0) return 0;
if(n==1) return 1;
int[] dp=new int[n+1];
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
/**
* 空间简化的从底向顶的计算
*/
public static int fib4(int n){
if(n==0) return 0;
if(n==1) return 1;
int LastLast=0;
int Last=1;
for(int i=2,cur;i<=n;i++){
cur=Last+LastLast;
LastLast=Last;
Last=cur;
}
return Last;
}
题目二：最低票价
代码：
package DynaticPractice;
import java.util.Arrays;
public class Problem2 {
//步骤数组,方案数组
public static int[] durations={1,7,30};
/**
* 方法一：暴力尝试
*/
public static int mincostTickets1(int[] days,int[] costs){
return f1(days,costs,0);
}
//从第i下标的天开始，最少花费多少
public static int f1(int[] days,int[] costs,int i){
if(i==days.length){//后续没有了
return 0;
}
int ans=Integer.MAX_VALUE;
for(int k=0,j=i;k<3;k++){//遍历方案
while (j<days.length && days[i]+durations[k]>days[j]){
j++;
}
ans=Math.min(ans,costs[k]+f1(days,costs,j));
}
return ans;
}
/**
* 带有缓存的递归
* 动态规划
*/
public static int mincostTickets2(int[] days,int[] costs){
int[] dp=new int[days.length];//dp数组中的元素值代表从该位置开始的最小费用
Arrays.fill(dp,Integer.MAX_VALUE);
return f2(days,costs,0,dp);
}
public static int f2(int[] days,int[] costs,int i,int[] dp){
if(i==days.length){//后续没有了
return 0;
}
if(dp[i]!=Integer.MAX_VALUE){
return dp[i];
}
int ans=Integer.MAX_VALUE;
for(int k=0,j=i;k<3;k++){//遍历方案
while (j<days.length && days[i]+durations[k]>days[j]){
j++;
}
ans=Math.min(ans,costs[k]+f2(days,costs,j,dp));
}
dp[i]=ans;
return ans;
}
/**
* 非递归方式
* 从底到顶的动态规划
*/
public static int MAXN=366;
public static int[] dp=new int[MAXN];
public static int mincostTickets3(int[] days,int[] costs){
int n=days.length;
Arrays.fill(dp,0,n+1,Integer.MAX_VALUE);
dp[n]=0;
for(int i=n-1;i>=0;i--){
for(int k=0,j=i;k<3;k++){
while (j<days.length && days[i]+durations[k]>days[j]){
j++;
}
dp[i]=Math.min(dp[i],costs[k]+dp[j]);
}
}
return dp[0];
}
}
题三：解码方法
代码：
package DynaticPractice;
import java.util.Arrays;
public class Problem3 {
/**
* 方法一
* @param s
* @return
*/
public static int numDecodings(String s){
return f1(s.toCharArray(),0);
}
private static int f1(char[] s, int i) {
if(i==s.length){
return 1;
}
int ans;
if(s[i]=='0'){
ans=0;
}else {
ans=f1(s,i+1);//自己单独一个字符的情况
if(i+1<s.length && ((s[i]-'0')*10+(s[i+1]-'0'))<=26){//两个字符的情况
ans+=f1(s,i+2);
}
}
return ans;
}
/**
* 方法二
*/
public static int numDecodings2(String s){
int[] dp=new int[s.length()];
Arrays.fill(dp,-1);
return f2(s.toCharArray(),0,dp);
}
private static int f2(char[] s, int i,int[] dp){
if(i==s.length){
return 1;
}
if(dp[i]!=-1){
return dp[i];
}
int ans;
if(s[i]=='0'){
ans=0;
}else {
ans=f2(s,i+1,dp);//自己单独一个字符的情况
if(i+1<s.length && ((s[i]-'0')*10+(s[i+1]-'0'))<=26){//两个字符的情况
ans+=f2(s,i+2,dp);
}
}
dp[i]=ans;
return ans;
}
/**
* 方法三
* 从底到顶
*/
public static int numDecodings3(String s){
char[] charArray = s.toCharArray();
int n=charArray.length;
int[] dp=new int[n+1];
dp[n]=1;
for(int i=n-1;i>=0;i--){
if(charArray[i]=='0'){
dp[i]=0;
}else{
dp[i]=dp[i+1];
if(i+1<charArray.length && ((charArray[i]-'0')*10+(charArray[i+1]-'0'))<=26){//两个字符的情况
dp[i]+=dp[i+2];
}
}
}
return dp[0];
}
}
