算法——动态规划-蒲公英云

文章目录

- - 1.斐波那契数列
  - - 1.1递归法
    - 1.2动态规划
    - 1.3优化法
  - 2.变态青蛙跳台阶
  - 3.最大连续子数组和
  - 4.字符串分割
  - 5.路径总数
  - 6.路径总数（有障碍版）
  - 7.最小路径和

1.斐波那契数列

1.1递归法

class Test{ 
    public int Fibonacci(int n){ 
        if(n<=0){ 
            return 0;
        }
        else if(n==1||n==2){ 
            return 1;
        }else
            return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

1.2动态规划

//初始状态：f(1)=f(2)=1
//状态递推：f(n)=f(n-1)+f(n-2)
//返回结果：f(n)
class Test{ 
    public int Fibonacci(int n){ 
        if(n<=0){ 
            return 0;
        }
        else if(n==1||n==2){ 
            return 1;
        }
        int [] a = new int [n+1];
        a[1]=a[2]=1;
        for(int i = 3;i<=n;i++){ 
            a[i]=a[i-1]+a[i-2];
        }
        return a[n];
    }
}

1.3优化法

class Test{ 
    public int Fibonacci(int n){ 
        if(n<=0){ 
            return 0;
        }
        else if(n==1||n==2){ 
            return 1;
        }
        int f1n=1;
        int f2n=1;
        int result = 0;
        for(int i = 3;i<=n;i++){ 
            result = f1n+f2n;
            f1n = f2n;
            f2n = result;
        }
        return result;
    }
}

2.变态青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

方法1：
跳n级台阶，第一步有n种跳法：
跳1级，剩下n-1级，跳法为F(n-1)
跳2级，剩下n-2级，跳法为F(n-2)
…
跳n级，剩下0级，跳法为F(0)
So,F(n) = F(n-1)+F(n-2)+…+F(0)
F(n-1) = F(n-2)+F(n-3)+…+F(0)
F(n) = 2*F(n-2)
-
F(1) = 1
F(2) = 2
F(3) = 4
…
F(n) = 2^(n-1)
方法2
除了最后一级台阶必须要跳之外，其余每级台阶都有两种可能，所以F(n) = 2^(n-1)

//方法1
class Test{ 
    public int jumpFloor(int n){ 
       return (int)Math.pow(2,n-1);
    }
}
//方法2
class Test{ 
    public int jumpFloor(int n){ 
       int total = 1;
       for(int i = 1;i<n;i++){ 
           total*=2;
       }
       return  total;
    }
}
//方法3
//降低时间复杂度 上述实现的时间复杂度:O(N) O(1)的实现：使用移位操作 
class Test{ 
    public int jumpFloor(int n){ 
        return  1<<(n-1);
    }
}

3.最大连续子数组和

子状态：以a[i]为末尾元素的子数组和的最大值
f(i) = max( f(i-1)+a[i] , a[i] )
f(i) = f(i-1)>0? f(i-1)+a[i] : a[i]
初始值：f(0) = a[0]
返回值：所有f(i)中的最大值

class Test{ 
    public int  FindGreatestSumOfSubArray(int [] a){ 
        int sum = a[0];
        int maxSum = a[0];
        for (int i = 1;i<a.length;i++){ 
            sum = sum>0 ? (sum+a[i]):a[i];
            maxSum = sum>maxSum ? sum :maxSum;
        }
        return maxSum;
    }
}

4.字符串分割

给定一个字符串s和一个词典dict，确定s是否可以根据词典中的词分成
一个或多个单词。
比如，给定
s = “leetcode”
dict = [“leet”, “code”]
返回true，因为”leetcode”可以被分成”leet code”

public class Solution { 
    public boolean wordBreak(String s, Set<String> dict) { 
        boolean [] a = new boolean [s.length()+1];
        a[0] = true;
        for (int i = 1;i <=s.length();i++){ 
            for (int j = 0;j<i;j++){ 
                if(a[j]&&dict.contains(s.substring(j,i))){ 
                    a[i]= true;
                    break;
                }
            }
        }
        return a[s.length()];
    }
   }

5.路径总数

在一个m*n的网格的左上角有一个机器人，机器人在任何时候只能向下或者向右移动，
机器人试图到达网格的右下角，有多少可能的路径。

public class Solution { 
    public int uniquePaths(int m, int n) { 
        int [][] a = new int [m][n];
        for(int i = 0;i<m;i++)
            a[i][0] = 1;
        for(int i = 0;i<n;i++)
            a[0][i] = 1;
        for(int i = 1;i<m;i++){ 
            for(int j = 1;j<n;j++){ 
                a[i][j] = a[i-1][j]+a[i][j-1];
            }
        }
        return a[m-1][n-1];
    }
}

6.路径总数（有障碍版）

机器人还是要从网格左上角到达右下角，但是网格中添加了障碍物，障碍物用1表示。

动态规划：
子状态：从（0,0）到（1,0）（1,1）…（m-1，n-1）…的路径总数
F(i,j)：从（0,0）到（i,j）的路径数
状态递推：
如果（i，j）=1，则总数为0，否则为F(i-1,j)+F(i,j-1)
特殊情况：第0行及第0列：1/0

public class Solution { 
    public int uniquePathsWithObstacles(int[][] obstacleGrid) { 
        int [][]a = new int [obstacleGrid.length][obstacleGrid[0].length];
        for(int i = 0;i<a.length;i++){ 
            if(obstacleGrid[i][0] == 1){ 
                break;
            }
            a[i][0] = 1;
        }
        for(int i = 0;i<a[0].length;i++){ 
            if(obstacleGrid[0][i] == 1){ 
                break;
            }
            a[0][i] = 1;
        }
        for(int i = 1;i<a.length;i++){ 
            for(int j = 1;j<a[0].length;j++){ 
                if(obstacleGrid[i][j] == 1){ 
                    a[i][j] = 0;
                }else{ 
                    a[i][j] = a[i-1][j]+a[i][j-1];
                }
            }
        }
        return a[a.length-1][a[0].length-1];
    }
}

7.最小路径和

给定一个m*n的网格，网格用非负数填充，找到一条从左上角到右下角的短路径。注：每次只能向下或者向右移动。

public class Solution { 
    public int minPathSum(int[][] grid) { 
        int [][]a = new int[grid.length][grid[0].length];
        a[0][0] = grid[0][0];
        for(int i=1;i<grid.length;i++){ 
            a[i][0] = a[i-1][0]+grid[i][0];
        }
        for(int i=1;i<a[0].length;i++){ 
            a[0][i] = a[0][i-1]+grid[0][i];
        }
        for(int i=1;i<a.length;i++){ 
            for(int j=1;j<a[0].length;j++){ 
                a[i][j] = Math.min(a[i-1][j],a[i][j-1])+grid[i][j];
            }
        }
        return a[a.length-1][a[0].length-1];
    }
  }