下面的題目是我刷的Leetcode上關(guān)于動(dòng)態(tài)規(guī)劃的題目，因?yàn)轭}還沒(méi)刷完翔曲，所以這篇文章會(huì)將不時(shí)地進(jìn)行續(xù)更

package cn.infobuy.gouqi.demo;

import java.util.List;

/**
 * 動(dòng)態(tài)規(guī)劃
 * @author JohnLiu
 */
public class DPSolution {
    /**
     * 給定一個(gè)整數(shù) n搀突，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種萎攒？
     * @param n
     * @return
     */
    public int numTrees(int n) {
        // numThrees(n)=numThrees(i-1)*numThrees(n-i);i=[2,n-1]
        if(n<=0){
            return 0;
        }
        int[] numThrees = new int[Math.max(n+1,3)];
        numThrees[0]=1;
        numThrees[1]=1;
        numThrees[2]=2;
        for(int nodeNum=3;nodeNum<n+1;nodeNum++){
            for(int j=1;j<=nodeNum;j++){
                numThrees[nodeNum]+=numThrees[j-1]*numThrees[nodeNum-j];
            }
        }
        return numThrees[n];
    }
    
    public int minCostClimbingStairs(int[] cost) {
        // dp(n)=Math.min(dp(n-1)+cost(n-1),dp(n-2)+cost(n-2))
        int dpp1=0,dpp2=0,dpcurr=0;
        for(int i=2;i<=cost.length;i++){
            dpcurr=Math.min(dpp2+cost[i-2],dpp1+cost[i-1]);
            dpp2=dpp1;
            dpp1=dpcurr;
        }
        return dpcurr;
    }
    /**
     * 給定一個(gè)僅包含 0 和 1 的二維二進(jìn)制矩陣让歼，找出只包含 1 的最大矩形，并返回其面積
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        
        
        return -1;
    }
    /**
     * 需要 n 步你才能到達(dá)樓頂
     * 每次你可以爬 1 或 2 個(gè)臺(tái)階
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int pre2Floor=1;
        int pre1Floor=2;
        if(n==1){
            return pre2Floor;
        }else if(n==2){
            return pre1Floor;
        }
        int currentFloor=0;
        for(int i=3;i<=n;i++){
            currentFloor = pre2Floor+pre1Floor;
            pre2Floor=pre1Floor;
            pre1Floor=currentFloor;
        }
        return currentFloor;
    }
    /**
     *  m x n 網(wǎng)格复凳，請(qǐng)找出一條從左上角到右下角的路徑瘤泪，使得路徑上的數(shù)字總和為最小
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int line = grid.length;
        int row = grid[0].length;
        int[] preLineMinPathSum = new int[row];
        //迭代第1行
        for(int i=0;i<row;i++){
            preLineMinPathSum[i]=i==0?grid[0][0]:grid[0][i]+preLineMinPathSum[i-1];
        }
        //迭代第2-n行
        int[] thisLineMinPathSum;
        for(int i=1;i<line;i++){
            thisLineMinPathSum=new int[row];
            thisLineMinPathSum[0]=preLineMinPathSum[0]+grid[i][0];
            for(int j=1;j<row;j++){
                if(thisLineMinPathSum[j-1]>preLineMinPathSum[j]){
                    thisLineMinPathSum[j]=preLineMinPathSum[j]+grid[i][j];
                }else{
                    thisLineMinPathSum[j]=thisLineMinPathSum[j-1]+grid[i][j];
                }
            }
            preLineMinPathSum=thisLineMinPathSum;
        }
        return preLineMinPathSum[row-1];
    }
    /**
     * 在有阻礙物的情況下
     * m x n 網(wǎng)格中從左上到右下有幾種走法
     * @param m
     * @param n
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /**
         * 阻礙物(i,k)表示：f((0,0),(i,k))=0;
         */
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[] preLinePaths=new int[m];
        // 迭代第1行的所有列
        for(int i=0;i<m;i++){
            if(i==0){
                preLinePaths[i]=obstacleGrid[0][i]==1?0:1;
            }else{
                preLinePaths[i]=obstacleGrid[0][i]==1?0:preLinePaths[i-1];
            }
        }
        // 迭代第2行-第n行的所有列
        int[] thisLinePaths;
        for(int line=1;line<n;line++){//line
            thisLinePaths=new int[m];
            thisLinePaths[0]=obstacleGrid[line][0]==1?0:preLinePaths[0];
            for(int r=1;r<m;r++){//row
                thisLinePaths[r]=obstacleGrid[line][r]==1?0:thisLinePaths[r-1]+preLinePaths[r];
            }
            preLinePaths=thisLinePaths;
        }
        return preLinePaths[m-1];
    }

    /**
     * m x n 網(wǎng)格中從左上到右下有幾種走法
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        // f(m,n)=f(m-1,n)+f(m,n-1)
        // f(0,0)=0,f(n,0)=1,f(0,n)=1
        //記錄上一行的所有走法
        int[] preLinePaths=new int[m];
        int[] thisLinePaths;
        for(int i=0;i<m;i++){
            preLinePaths[i]=1;
        }
        for(int l=1;l<n;l++){//第幾行 line
            thisLinePaths=new int[m];
            thisLinePaths[0]=1;
            for(int r=1;r<m;r++){//第幾列 row
                thisLinePaths[r]=thisLinePaths[r-1]+preLinePaths[r];
            }
            preLinePaths=thisLinePaths;
        }
        return preLinePaths[m-1];
    }
    /**
     * 求最大子序和
     * 當(dāng)數(shù)組中存在非負(fù)數(shù)的元素，最大子序和的起點(diǎn)一定大于0
     * @param nums
     * @return maxSum
     */
    public int maxSubArray(int[] nums) {
        int maxSum = 0;
        int thisSum = 0;
        int singleMax = nums[0];
        //假設(shè)數(shù)組中的元素存在非負(fù)數(shù)
        for(int i = 0;i<nums.length;i++){
            thisSum+=nums[i];
            if(thisSum>maxSum){
                maxSum=thisSum;
            }
            if(thisSum<0){
                thisSum=0;
            }
            if(nums[i]>singleMax){
                singleMax=nums[i];
            }
        }
        if(maxSum==0){
            //說(shuō)明數(shù)組中的元素均為非正數(shù)
            return singleMax;
        }else{
            return maxSum;
        }
    }
    /**
     * 最長(zhǎng)上升子序列
     * 給定一個(gè)無(wú)序的整數(shù)數(shù)組育八，找到其中最長(zhǎng)上升子序列的長(zhǎng)度对途。
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        /**
         * 雖然求的是一個(gè)整數(shù)數(shù)組的最長(zhǎng)上升子序列，但是dp的是髓棋，當(dāng)子序列包含數(shù)組最后一個(gè)元素的LIS長(zhǎng)度
         * int[] lis 記錄截止點(diǎn)到index時(shí)的序列的LIS的長(zhǎng)度
         * f(n) = Math.max(f(n-i),f(n-k),f(n-m),,,)+1 {當(dāng) nums[n]>nums[n-i],nums[n-j],nums[n-k]}
         * 時(shí)間復(fù)雜度為 O(n^2)
         * 
         */
        if(nums.length==0) {
            return 0;
        }
        int[] lis = new int[nums.length];
        lis[0]=1;
        int maxLIS = lis[0];
        for(int i=1;i<nums.length;i++) {
            lis[i]=1;
            // 這一步特別耗時(shí)实檀，其實(shí)不需要每次都查找一遍
            // 存起來(lái)就可以
            for(int j=0;j<i;j++) {
                if(nums[i]>nums[j]) {
                    lis[i]=Math.max(lis[i], lis[j]+1);
                }
            }
            if(maxLIS<lis[i]) {
                maxLIS=lis[i];
            }
        }
        return maxLIS;
    }
    /**
     * 最大正方形
     * 備注：當(dāng)dp[][]記錄矩陣右上角
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        // dp[][] 記錄以(x,y)為矩形右上角的邊長(zhǎng)
        int xlen = matrix.length;
        if(xlen==0) {
            return 0;
        }
        int ylen = matrix[0].length;
        int[][] dp = new int[xlen][ylen];
        int maxVas = 0;
        // 設(shè)定縱向第一列
        for(int y=0;y<ylen;y++) {
            dp[0][y]=matrix[0][y]-48;
            maxVas=Math.max(maxVas,dp[0][y]);
        }
        // 設(shè)定橫向第一列
        for(int x=0;x<xlen;x++) {
            dp[x][0] = matrix[x][0]-48;
            maxVas=Math.max(maxVas,dp[x][0]);
        }
        for(int x=1;x<xlen;x++) {
            for(int y=1;y<ylen;y++) {
                if(matrix[x][y]=='1') {
                    // 狀態(tài)轉(zhuǎn)移
                    dp[x][y]=Math.min(Math.min(dp[x-1][y-1],dp[x-1][y]),dp[x][y-1])+1;
                    maxVas=Math.max(maxVas, dp[x][y]);
                }
            }
        }
        return maxVas*maxVas;
    }
    /**
     * 丑數(shù) II
     * 丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。
     * number = 2^i*3^j*5^k (i>=0,j>=0,k>=0) 
     *  1, 2, 3, 4, 5, 6, 8, 9, 10, 12
     *  
     *  狀態(tài)轉(zhuǎn)移方程：f(n) = Math.min(f(i)*2,f(j)*3,f(k)*5) // i,j,k從0開始不斷累加
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        int[] uglyNumbers = new int[n];
        int num_2=0;
        int num_3=0;
        int num_5=0;
        uglyNumbers[0]=1;
        for(int i=1;i<n;i++){
            uglyNumbers[i] = Math.min(Math.min(uglyNumbers[num_2]*2, uglyNumbers[num_3]*3),uglyNumbers[num_5]*5);
            if(uglyNumbers[i]==uglyNumbers[num_2]*2){
                num_2++;
            }
            if(uglyNumbers[i]==uglyNumbers[num_3]*3){
                num_3++;
            }
            if(uglyNumbers[i]==uglyNumbers[num_5]*5){
                num_5++;
            }
        }
        return uglyNumbers[n-1];
    }
    /**
     * 給定一個(gè)三角形按声，找出自頂向下的最小路徑和膳犹。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int line = triangle.size();
        int edge = triangle.get(line-1).size();
        int[][] dp = new int[line][edge];
        dp[0][0]=triangle.get(0).get(0);
        for(int i=1;i<line;i++){
            List<Integer> thisLine = triangle.get(i);
            for(int j=0;j<triangle.get(i).size();j++){
                if(j==0){
                    dp[i][j]=dp[i-1][0];
                }else if(j==thisLine.size()-1){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j]);
                }
                dp[i][j]+=thisLine.get(j);
            }
        }
        int minimumTotal=Integer.MAX_VALUE;
        for(int j=0;j<dp[line-1].length;j++){
            minimumTotal=Math.min(minimumTotal,dp[line-1][j]);
        }
        return minimumTotal;
    }
    public int minimumTotal2(List<List<Integer>> triangle) {
        int line = triangle.size();
        // 自底向上保留記錄的值
        // 好處1：不會(huì)覆蓋之后要參與計(jì)算的值
        // 好處2：最后的dp[0]就是最小值，不需要再進(jìn)行遍歷得出
        int[] dp = new int[line+1];
        for(int i=line-1;i>=0;i--){
            List<Integer> thisLine = triangle.get(i);
            for(int j=0;j<=i;j++){
                dp[j]=Math.min(dp[j], dp[j+1])+thisLine.get(j);
            }
        }
        return dp[0];
    }
    /**
     * 買賣股票的最佳時(shí)機(jī)
     * 最多只允許完成一筆交易
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int[] profits = new int[prices.length-1];
        // 求出最大子序和
        int maxProfit=0;
        int tmpProfit=0;
        for(int i=0;i<profits.length;i++){
            // 求出每天的利潤(rùn)空間
            profits[i]=prices[i+1]-prices[i];
            tmpProfit+=profits[i];
            if(tmpProfit<0){
                tmpProfit=0;
            }else if(tmpProfit>maxProfit){
                maxProfit=tmpProfit;
            }
        }
        return maxProfit;
    }
    /**
     * 買賣股票的最佳時(shí)機(jī) IV
     * 你最多可以完成 k 筆交易
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {
        
        
        return k;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}