//解法一：
public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    return fib[n];
}

//解法二：是对解法一的优化
public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int pre1 = 0, pre2 = 1;
    int fib = 0;
    for (int i = 2; i <= n; i++) {
        fib = pre1 + pre2;
        pre1 = pre2;
        pre2 = fib;
    }
    return fib;
}

public int JumpFloor(int target) {
    if(target<=2){
        return target;
    }
    int pre1 = 1;
    int pre2 = 2;
    for(int i=3;i<=target;i++){
        int next = pre1 + pre2;
        pre1 = pre2;
        pre2 = next;
    }
    return pre2;
}

//思路一：
// 公式法
// 跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去... ，那么
// f(n) = f(n-1) + f(n-2) + ... + f(0)							(I)
// 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么
// f(n-1) = f(n-2) + f(n-3) + ... + f(0)						(II)
// (I) - (II) 式，可得
// f(n) - f(n-1) = f(n-1)
// 即
//f(n) = 2*f(n-1)

public int JumpFloorII(int target) {
    return (int) Math.pow(2, target - 1);
}

//思路二：
//动态规划：dp[i] 表示跳上 i 级别的台阶总共的跳法
//思路一种 f(n) = 2*f(n-1) 
//这里就是 dp[i] = 2*dp[i-1]

public int JumpFloorII(int target) {
    if(target<=1){
        return target;
    }

    //dp[i] 表示跳上 i 级别的台阶总共的跳法
    int[] dp = new int[target+1];
    Arrays.fill(dp,1);

    for(int i=2;i<=target;i++){
        dp[i] = 2*dp[i-1];
    }
    return dp[target];
}

public int RectCover(int target) {
    if (target==1){
        return 1;
    }
    if(target==2){
        return 2;
    }
    int pre1 = 1;
    int pre2 = 2;

    int res = 0;
    for(int i=3;i<=target;i++){
        res = pre1 + pre2;
        pre1 = pre2;
        pre2 = res;
    }
    return res;
}

//思路：
//动态规划思路
//dp[i] 表示以 array[i] 结尾的元素连续子数组的最大连续和
//dp[i-1]>0 时，dp[i] = dp[i-1] + array[i]
//否则，dp[i] = array[i]

//写法一：
//时间复杂度：O(n)
//空间复杂度：O(n)
//连续子数组的最大和
public int FindGreatestSumOfSubArray(int[] array) {
    if(array.length==1){
        return array[0];
    }
    int n = array.length;
    //dp[i] 表示以array[i]结尾的元素连续子数组的最大连续和
    int[] dp = new int[n];
    dp[0] = array[0];

    int res= Integer.MIN_VALUE;

    for(int i=1;i<n;i++){
        if(dp[i-1]>0){
            dp[i] =dp[i-1]+array[i]; //array[i] 加上任意一个 > 0 的数都会大于原来的数
        }else{
            dp[i] = array[i];
        }
        res = Math.max(res,dp[i]);
    }
    return res;
}

//写法二:
//时间复杂度：O(n)
//空间复杂度：O(1)
public int FindGreatestSumOfSubArray(int[] array) {
    if(array.length==1){
        return array[0];
    }
    int n = array.length;

    int pre1 = array[0];

    int res= Integer.MIN_VALUE;

    for(int i=1;i<n;i++){
        int pre2 = (pre1>0)?(pre1+array[i]):array[i];
        pre1 = pre2;
        res = Math.max(res,pre2);
    }
    return res;
}

//思路：
//第一个是 1，接下来可以是 1 * 2 , 1 * 3 , 1 * 5，此时最小的显然是 2
//第二个是 2，接下来可以是 2 * 2 , 2 * 3 , 2 * 5，此时就要把这次得到的三个 4,6,10 和上一次剩下的两个3,5 比较大小，找出最小的，即 3
//第三个是 3，接下来可以是 3 * 2 , 3 * 3 , 3 * 5
//...

public int GetUglyNumber_Solution(int index) {
    if(index<=1){
        return index;
    }
    int[] dp = new int[index+1];
    dp[1] = 1;
    int i2 = 1, i3 = 1, i5 = 1;
    for(int i=2;i<=index;i++){
        int next2=dp[i2]*2;
        int next3=dp[i3]*3;
        int next5=dp[i5]*5;
        dp[i] = min3(next2,next3,next5);
        if(dp[i]==next2){
            i2++;
        }
        if(dp[i]==next3){
            i3++;
        }
        if(dp[i]==next5){
            i5++;
        }
    }
    return dp[index];
}

private int min3(int a,int b,int c){
    int tmp = a<b?a:b;
    return (tmp<c)?tmp:c;
}

//思路：
//动态规划
//dp[i] 表示将 i 分割成几个整数的最大成乘积和

public int integerBreak(int n) {
    if(n==1){
        return 0;
    }

    //dp[i] 表示将 i 分割成几个整数的最大成乘积和
    int[] dp = new int[n+1];
    dp[1] = 0;
    dp[2] = 1;

    for(int i=3;i<=n;i++){
        for(int j=1;j<i;j++){
            dp[i] = max3(dp[i],j*(i-j),j*dp[i-j]);
        }
    }
    return dp[n];
}

private int max3(int a,int b,int c){
    int tmp=a>b?a:b;
    return tmp>c?tmp:c;
}

@Test
public void test(){
    int n=10;
    System.out.println(integerBreak(n));
}