动态规划（Dynamic Programming）

2023-12-17 17:48:06

动态规划（Dynamic Programming）：是运筹学的一种最优化方法，只不过在计算机问题上应用比较多

DP常见步骤：

暴力递归/穷举
记忆化搜索（傻缓存?+ 递归）,使用备忘录/ DP Table 来优化穷举过程
严格表结构（整理缓存之间的关系，如dp[i] = dp[i - 1]）

例子

509.斐波那契数

1.暴力递归

int fib(int N) {
    if (N == 1 || N == 2){
    return 1;
    }
    return fib(N - 1) + fib(N - 2);
}

2.记忆化搜索（加缓存）

int fib(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return dp(memo, N);
}

// 带着备忘录进行递归
int dp(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

3.严格表结构（缓存+状态转移方程）

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

4.空间压缩（优化）

由状态转移方程可知，f(n) 只和 f(n-1) 和 f(n-2) 有关，使用「滚动数组思想」可以把空间复杂度优化成?O(1)

    int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }

基础类DP

70.爬楼梯

经典动态规划

class Solution {
    public int climbStairs(int n) {
        if (n == 1){
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

空间压缩

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int prev = 1;
        int cur = 2;
        int next = 0;
        for (int i = 3; i <= n; i++) {
            next = cur + prev;
            prev = cur;
            cur = next;
        }
        return cur;
    }
}

746.使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 2];
        dp[1] = 0;
        dp[2] = 0;
        for (int i = 3; i <= cost.length + 1; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 2], dp[i - 2] + cost[i - 3]);
        }
        return dp[cost.length + 1];
    }
}

空间压缩

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int prev = 0;
        int cur = 0;
        int next = 0;
        for (int i = 2; i <= cost.length; i++) {
            next = Math.min(prev + cost[i - 2], cur + cost[i - 1]);
            prev = cur;
            cur = next;
        }
        return cur;
    }
}

62.不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[][] dp = new int[m][n];

        // base case
        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];
    }
}

?路径压缩

class Solution {
    public int uniquePaths(int m, int n) {
       if (m <= 0 || n <= 0) {
            return 0;
        }
        int[] dp = new int[n];

         // base case
        Arrays.fill(dp, 1);

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

63.不同路径 II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[][] dp = new int[row][col];

        for (int i = 0; i < row; i++) {
            if (obstacleGrid[i][0] == 1){
                break;
            }
            dp[i][0] = 1;
        }

        for (int i = 0; i < col; i++) {
            if (obstacleGrid[0][i] == 1){
                break;
            }
            dp[0][i] = 1;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[row - 1][col - 1];
    }
}

空间压缩

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            return 0;
        }
        int[] dp = new int[col];
        dp[0] = 1;
        for (int j = 1; j < col; j++) {
            if (obstacleGrid[0][j] == 1) {
                break;
            }
            dp[j] = 1;
        }

        for (int i = 1; i < row; i++) {
            dp[0] = (obstacleGrid[i][0] == 1 || dp[0] == 0) ? 0 : 1;
            for (int j = 1; j < col; j++) {
                dp[j] = obstacleGrid[i][j] == 1 ? 0 : dp[j] + dp[j - 1];
            }
        }
        return dp[col - 1];
    }
}

64.最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row][col];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int i = 1; i < col; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }

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

空间压缩

class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        int[] dp = new int[col];

        dp[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            dp[i] = grid[0][i] + dp[i - 1];
        }

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

0-1背包类DP

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的0和1，这类问题便被称为「0-1 背包问题」。

01背包最重要的是如何识别出来为01背包，一般是有一个目标堆，对于数组的元素有留和舍两种选择，通过数组值的取舍进行达到目标堆的目的
背包问题进行空间压缩时，weight 的循环要从大到小遍历，否则会造成前段值覆盖引起的答案错误。

416.分割等和子集

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int max = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, num);
        }
        int half = sum / 2;
        if (((sum & 1) == 1) || max > half){
            return false;
        }
        
        boolean[][] dp = new boolean[nums.length][half + 1];
        // base case
        dp[0][0] = true; // 第一个元素不选，容量为0时满足的
        dp[0][nums[0]] = true; // 选择第一个元素

        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= half; j++) {
                // 不选择 num[i]
                dp[i][j] = dp[i-1][j];
                // 保证下标不越界
                if (j - nums[i] >= 0){
                    // 选择 num[i], 看是否能在 [0, i - 1] 这个子区间内找到一部分元素，使得它们的和为 j - nums[i]
                    dp[i][j] |= dp[i - 1][j - nums[i]];
                }
            }
            // 由于状态转移方程的特殊性，提前结束，可以认为是剪枝操作
            if (dp[i][half]) {
                return true;
            }
        }
        return dp[nums.length - 1][half];
    }
}

空间压缩

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int max = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, num);
        }
        int half = sum / 2;
        if (((sum & 1) == 1) || max > half) {
            return false;
        }

        boolean[] dp = new boolean[half + 1];

        dp[0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = half; j >= nums[i]; j--) {
                dp[j] |= dp[j - nums[i]];
            }
            if (dp[half]) {
                return true;
            }
        }
        return dp[half];
    }
}

494.目标和

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(sum) < Math.abs(target)) {
            return 0;
        }
        // 因为包含了负数和 0, range: [-sum, sum]
        int range = 2 * sum + 1;
        int[][] dp = new int[nums.length][range];

        dp[0][sum - nums[0]] += 1;
        dp[0][sum + nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = -sum; j <= sum; j++) {
                if (j + nums[i] > sum) {    // 超过 [-sum, sum] 的范围，只能减
                    dp[i][j + sum] = dp[i - 1][j - nums[i] + sum];
                } else if (j - nums[i] < -sum) { // 超过 [-sum, sum] 的范围，只能加
                    dp[i][j + sum] = dp[i - 1][j + nums[i] + sum];
                } else {
                    dp[i][j + sum] = dp[i - 1][j - nums[i] + sum] + dp[i - 1][j + nums[i] + sum];
                }
            }
        }
        return dp[nums.length - 1][sum + target];
    }
}

474.一和零

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];

        for (int i = 1; i <= strs.length; i++) {
            int zeros = containsZero(strs[i - 1]);
            int ones = strs[i - 1].length() - zeros;
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= zeros && k >= ones){
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1);
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

     private int containsZero(String str) {
        int res = 0;
        for (char c : str.toCharArray()) {
            if (c == '0') {
                res++;
            }
        }
        return res;
    }
}

空间压缩

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= strs.length; i++) {
            int zeros = containsZero(strs[i - 1]);
            int ones = strs[i - 1].length() - zeros;
            for (int j = m; j >= 0; j--) {
                for (int k = n; k >= 0; k--) {
                    if (j >= zeros && k >= ones){
                        dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
                    }
                }
            }
        }
        return dp[m][n];
    }

     private int containsZero(String str) {
        int res = 0;
        for (char c : str.toCharArray()) {
            if (c == '0') {
                res++;
            }
        }
        return res;
    }
}

文章来源:https://blog.csdn.net/weixin_46058921/article/details/135044920
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！