动态规划、背包问题 6/24 106-110

1.买卖股票的最佳时机含手续费(LeetCode 714)

动态规划
此题同
买卖股票的最佳时机II（ LeetCode 122 ）
思想相似

class Solution {
    
        public int maxProfit(int[] prices, int fee) {
    
            if (prices.length < 1)return 0;
            int buy = -prices[0];//第i天结束手中持有股票的最大利润
            int sell = 0;//第i天结束手中未持有股票的最大利润
            for (int i = 1; i < prices.length; i++) {
    
                int preBuy = buy;
                buy = Math.max(buy,sell - prices[i]);
                sell = Math.max(sell,preBuy + prices[i] - fee);
            }
            return sell;
        }
    }

2.完全平方数（ LeetCode 279 ）

解法一：完全背包 朴素数组

class Solution {
    
        public int numSquares(int n) {
    
            if (n < 2)return n;
            List<Integer> list = new ArrayList<>();
            //寻找小于n的所有完全平方数
            for (int i = 1; i * i <= n; i++) list.add(i * i);
            //dp[i][j] 前i个数中进行寻找，凑成j的最小数量
            int[][] dp = new int[list.size()][n + 1];
            //初始化
            for (int i = 0; i <= n; i++) {
    
                dp[0][i] = i;
            }
            for (int i = 1; i < list.size(); i++) {
    
                for (int j = 0; j <= n; j++) {
    
                    //不选第i个元素
                    int no = dp[i - 1][j];
                    //选第i个元素
                    int yes = Integer.MAX_VALUE;
                    //第i个元素可选0 ~ k次
                    for (int k = 1; ; k++) {
    
                        if (k * list.get(i) > j)break;
                        yes = Math.min(yes,dp[i - 1][j - k * list.get(i)] + k);
                    }
                    dp[i][j] = Math.min(no,yes);
                }
            }
            return dp[list.size() - 1][n];
        }
    }

解法二：完全背包 一维数组优化

 class Solution {
    
        public int numSquares(int n) {
    
            if (n < 2)return n;
            List<Integer> list = new ArrayList<>();
            for (int i = 1; i * i <= n; i++) list.add(i * i);
            int[] dp = new int[n + 1];
            //初始化
            for (int i = 0; i <= n; i++) {
    
                dp[i] = i;
            }
            for (int i = 1; i < list.size(); i++) {
    
                int num = list.get(i);
                for (int j = 0; j <= n; j++) {
    
                    //不选当前元素
                    int no = dp[j];
                    //选当前元素
                    int yes = j >= num ? dp[j - num] + 1 : Integer.MAX_VALUE;
                    dp[j] = Math.min(no,yes);
                }
            }

            return dp[n];
        }
    }

解法三：官方解 动态规划

class Solution {
    
        public int numSquares(int n) {
    
            /* dp[i] : 构成数字i所需最少的平方数 dp[i] = 1 + Ma.min( dp[i - j * j] ) ,其中 0 < j <= 根号i */
           int[] dp = new int[n + 1];
            for (int i = 1; i <= n; i++) {
    
                int min = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) {
    
                    min = Math.min(min,dp[i - j * j]);
                }
                dp[i] = min + 1;
            }
            return dp[n];
        }
    }

3.三角形最小路径和（ LeetCode 120 ）

动态规划

class Solution {
    
    public int minimumTotal(List<List<Integer>> triangle) {
    
        int n = triangle.size();
        //f[i][j] 到达第i行j列的最短距离
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
    
            //每行的第一个元素与最后一个元素特殊对待
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
    
                //状态转移方程
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        //寻找最后一行的最小值
        int minTotal = f[n - 1][0];
        for (int i = 1; i < n; ++i) {
    
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }
}

4.不同路径（ LeetCode 62 ）

动态规划

class Solution {
    
        public int uniquePaths(int m, int n) {
    
            int[][] dp = new int[m][n];
            //初始化第一行
            for (int i = 0; i < n; i++) {
    
                dp[0][i] = 1;
            }
            //初始化第一列
            for (int i = 0; i < m; i++) {
    
                dp[i][0] = 1;
            }
            for (int i = 1; i < m; i++) {
    
                for (int j = 1; j < n; j++) {
    
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m - 1][n - 1];
        }
    }

方法二：动态规划　优化空间复杂度

class Solution {
    
        public int uniquePaths(int m, int n) {
    
            int[] dp = new int[n];//保存上一行的每个位置的结果
            //初始化第一行
            for (int i = 0; i < n; i++) {
    
                dp[i] = 1;
            }
 
            for (int i = 1; i < m; i++) {
    
                int left = 1;//保存当前位置左侧的数值
                for (int j = 1; j < n; j++) {
    
                    dp[j] = left + dp[j];
                    left = dp[j];
                }
            }
            return dp[n - 1];
        }
    }

5.不同路径II（ LeetCode 63 ）

动态规划

   class Solution {
    
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
            if (obstacleGrid[0][0] == 1)return 0;//特殊情况，第一个元素处就堵塞
            dp[0][0] = 1;//边界条件
            //初始化第一行
            for (int i = 1; i < n; i++) {
    
                if (obstacleGrid[0][i] == 1){
    //此处不通直接置0
                    dp[0][i] = 0;
                }else {
    
                    dp[0][i] = dp[0][i - 1];//等于前一处的方案数
                }
            }
            //初始化第一列
            for (int i = 1; i < m; i++) {
    
                 if (obstacleGrid[i][0] == 1){
    
                     dp[i][0] = 0;
                 }else {
    
                     dp[i][0] = dp[i - 1][0];
                 }
            }
            //计算其他行
            for (int i = 1; i < m; i++) {
    
                for (int j = 1; j < n; j++) {
    
                  if (obstacleGrid[i][j] == 1){
    
                      dp[i][j] = 0;
                  }else {
    
                      dp[i][j] = dp[i][j - 1] + dp[i - 1][j];//转移方程
                  }
                }
            }
            return dp[m - 1][n - 1];
        }
    }

方法二：动态规划
优化空间复杂度

class Solution {
    
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[] dp = new int[n];//某一行中的元素对应的路径数
            if (obstacleGrid[0][0] == 1)return 0;
            dp[0] = 1;
            //初始化第一行
            for (int i = 1; i < n; i++) {
    
                if (obstacleGrid[0][i] == 1){
    
                    dp[i] = 0;
                }else {
    
                    dp[i] = dp[i - 1];
                }
            }
            for (int i = 1; i < m; i++) {
    
                //首元素单独计算
                if (obstacleGrid[i][0] == 1){
    
                    dp[0] = 0;
                }
                for (int j = 1; j < n; j++) {
    
                    if (obstacleGrid[i][j] == 1)
                        dp[j] = 0;
                    else 
                        dp[j] = dp[j] + dp[j - 1];
                }
            }
            return dp[n - 1];
        }
    }