算法核心-动态规划算法

分析&回答

动态规划算法将待求解问题拆分成一系列相互交叠的子问题，通过递推关系定义各子问题的求解策略，并随时记录子问题的解，最终获得原始问题的解，避免了对交叠子问题的重复求解。

在动态规划算法中有三要素：

1. 最优子结构: 是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
2. 边界: 是指问题最小子集的解
3. 状态转移函数: 是指从一个阶段向另一个阶段过渡的具体模式，描述的是两个相邻子问题之间的关系

动态规划算法解决问题 （接雨水）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

动态规划算法解决问题 （爬楼梯）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

动态规划算法解决问题 （买卖股票的最佳时机）

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        int[] have = new int[len];  // 表示第i天持有股票所得最多现金
        int[] no = new int[len];    // 表示第i天不持有股票所得最多现金
        have[0] = -prices[0]; // 此时的持有股票就一定是买入股票了
        no[0] = 0;            // 不持有股票那么现金就是0

        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i-1], -prices[i]);
            no[i] = Math.max(no[i-1], prices[i] + have[i-1]);
        }
        return no[len - 1];
    }
}

题目代码出自LeetCode，请自行查阅。

反思&扩展

其他应用

• 爬楼梯问题
• 背包问题
• 最长递归子序列(回文串)问题