V2CE – 算法(三) 动态规划

动态规划

  • 利用历史记录(子问题的结果)来避免重复计算。
  • 历史记录需要用一些变量来保存，一维数组和二维数组比较多。

俺的做题步骤

  1. 明确dp数组的含义，也就是对历史记录的定义。
  2. 找出数组元素间的关系，如dp[n] = dp[n-1] + dp[n-2]。
  3. 找出初始值，因为关系式需要一个初始值进行结束。但是一定要找全！

例题

1，买卖股票最佳时间(智商题，动态规划)

来自 LeetCode121

解法

1，智商题

  • 本题除了要求大数在小数后面，没有其他要求（如长度，时间等都没有要求）。
  • 所以可以得出，只需要得到前面最小值和后面的最大值，双方差值一定为最大利润。
  • 且因为被限制大数在小数后面的问题，所以该方法不会出现遗漏。（出现比原定min更小的数字时，如果后面有能使max更大的数，取原来的min利润一定会小于新取的min利润）
class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int now : prices){
            if(now<min)
                min = now;
            else if(now - min > max)
                max = now - min;
        }
        return max;
    }
}

2，动态规划

  • 俺的粗糙解法
class Solution {
    public int maxProfit(int[] prices) {
        int min;
        int[] dp = new int[prices.length];
        if(prices.length==1)
            return 0;

        dp[0]=0;
        if(prices[1]>prices[0]){
            dp[1] = prices[1] - prices[0];
            min = prices[0];
        }
        else{
            dp[1] = 0;
            min = prices[1];
        }
        

        for(int i = 2;i<prices.length;i++){
             if(prices[i]<min)
                min = prices[i];
            dp[i] = Math.max(dp[i-1],prices[i]-min);
         }
         return dp[prices.length-1];
    }
}

很粗糙，空间复杂度O(m*n)，太高。需要进行动态规划的优化算法。

  • 大佬解法
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int min = prices[0], max = 0;
        for(int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return max;
    }
}

理解（不保证正确）

无

2，不同路径

来自LeetCode62

解法

1，俺的动态规划

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for(int i = 0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int i = 0;i<n;i++){
            dp[0][i] = 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];
    }
}

空间复杂度为m*n，需要进一步优化。

2，动态规划优化后

待补充。

理解

  • 务必先确定dp数组的定义和初始值要哪些！！！！

3,最小路径和（不同路径的不同方向）

来自 LeetCode 64

解法

1，俺的动态规划

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i = 1;i<grid[0].length;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i]; 
        }

        for(int j = 1;j<grid.length;j++){
            dp[j][0] = dp[j-1][0] + grid[j][0];
        }

        for(int i = 1;i<grid.length;i++){
            for(int j = 1;j<grid[0].length;j++){
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j];
            }
        }

        return dp[grid.length-1][grid[0].length-1];

    }
}

空间复杂度0(m*n)，可以优化。

2，动态规划优化。

学了再搞。

理解

无。

正文完
2022-06-09