Skip to content

Latest commit

 

History

History
282 lines (162 loc) · 9.19 KB

动态规划.md

File metadata and controls

282 lines (162 loc) · 9.19 KB
Raw

动态规划DP

动态规划（英语：Dynamic programming，简称 DP），通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。复杂问题不能分解成几个子问题，而分解成一系列子问题 ；

DP通常基于一个递推公式及一个(或多个)初始状态，当前子问题解由上一次子问题解推出。

动态规划算法的关键在于解决冗余，以空间换时间的技术，需要存储过程中的各种状态。可以看着是分治算法+解决冗余

动态规划算法也可以说是 记住求过的解来节省时间 ; 比如 Fibonacci数列 中，先直接从最小，最简单的 f(1) , f(2) 开始，自低向上一直到 f(20) , 这就是动态规划的思路

【初始状态】→【决策1】→【决策2】→…→【决策n】→【结束状态】

DP 应用场景

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

使用动态规划算法的问题的特征是子问题的重叠性，最优子结构 ，否则动态规划算法不具备优势。

动态规划的核心思想就是穷举求最值； 动态规划问题的一般形式就是求最值,动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说：

  • Fibonacci数列 代码参考这里 递归

  • 最大子数组和

  • 凑零钱问题

  • 股票问题 代码参考这里

  • 打家劫舍问题 : num[i] 代表第i个房子中的现金数目，从房子中取钱的最大数目，约束是相邻房子的钱不能同时取出

  • 接雨水问题 ：num[i]表示柱子高度，计算下雨之后能接多少雨水

  • 青蛙跳阶问题： 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

  • 最小编辑距离

  • 最长递增子序列 （LIS Longest Increasing Subsequence），如【5，6，7，3，2，8】 最长子序列 【5，6，7，8】, 输出4

  • 最长公共子序列 （LIS Longest public Subsequence）

  • 最长回文子序列 （LIS Longest public Subsequence）

  • 0-1 背包问题

[更多动态规划案例代码实现参考deep-in-java])(https://github.com/nonstriater/deep-in-java/tree/master/src/main/java/com/nonstriater/deepinjava/algo/framework/dynamic)

青蛙跳阶问题

想跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去;要么是先跳到第8级，然后一次迈2级台阶上去。
同理，要想跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去;要么是先跳到第7级，然后一次迈2级台阶上去。
要想跳到第8级台阶，要么是先跳到第7级，然后再跳1级台阶上去;要么是先跳到第6级，然后一次迈2级台阶上去

即通用公式为: f(n) = f(n-1) + f(n-2)

那f(2) 或者 f(1) 等于多少呢？

当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;
当只有1级台阶时，只有一种跳法，即f（1）= 1；

DP VS 分治法

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。

DP VS 回溯法

DP 和 回溯法 都会用到递归

动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划；而有些问题没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的

DP 解题模板

基本步骤

  • 划分问题
  • 状态定义， 穷举「状态」， bad case
  • 状态转移方程, 这一步最为困难 ; 暴力解法就是状态转移方程
  • 状态压缩
# 初始化 base case
dp[0][0][...] = base

# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

最大子数组和

示例： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，连续子数组 [4,-1,2,1] 的和最大， 输出：6

dp[i] 表示 nums[i] 为结尾的「最大子数组和」; dp[n-1] 就是 nums 的「最大子数组和」 状态转移 : dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); 状态压缩：注意到 dp[i] 仅仅和 dp[i-1] 的状态有关

public static int largestSubSequenceSum2(int[] nums){

        int n = nums.length;
        if (n == 0) return 0;

        // base case
        int dp_0 = nums[0];
        int dp_1 = 0;
        int res = dp_0;

        for (int i = 1; i < n; i++) {
            // dp[i] = max(nums[i], nums[i] + dp[i-1])
            dp_1 = Math.max(nums[i], nums[i] + dp_0);
            dp_0 = dp_1;

            // 顺便计算最大的结果, 保存到 res
            res = Math.max(res, dp_1);
        }

        return res;

    }

凑零钱问题

凑零钱问题视频解读参考这里 实现代码这里

如果使用贪心策略，并不能得到最优解。

比如：给定一个面值list ： 1，2，4，5，7，10； 给定一个 target ： 14， 求 凑齐 target=14 , 最少的零钱数量

思路：

如想求 amount = 14 时的最少硬币数， 如果你知道凑出 amount = 13 的最少硬币数（子问题）， 再加 1 个 1元面值 即可 如果你知道凑出 amount = 12 的最少硬币数（子问题）， 再加 1 个 2元面值 即可 如果你知道凑出 amount = 10 的最少硬币数（子问题）， 再加 1 个 4元面值 即可 如果你知道凑出 amount = 9 的最少硬币数（子问题）， 再加 1 个 5元面值 即可

for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);
            // 子问题无解则跳过
            if (subProblem == -1) continue;

            // 在子问题中选择最优解，然后加一
            res = Math.min(res, subProblem + 1);
        }

通过备忘录消除子问题(不用递归了), dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出 如想求 amount = 14 时的最少硬币数, dp[14] dp[0] = 0 dp[1] = 1 dp[2] = 1个2元的，dp[1] + 1个1元 ... dp[9] = dp[8] + 1个1元， dp[7] + 1个2元， dp[5] + 1个4元， dp[4] + 1个5元，dp[2] + 1个7元
1 + dp[i-coin] 从这些可选项里选择最小的

//对于 dp[i], 遍历可选项, 选择最小的
for(int coin : coins) {
    if (i < coin) {
        continue;
    }

    //dp[i] 保留最小的
    dp[i] = Math.min(dp[i],dp[i-coin] + 1 ) 
}

完整代码如下：

//递归解法，处理重叠子问题, 使用 dp[amount+1] 备忘录
 int coinChange2(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        // 数组大小为 amount + 1，初始值也为 amount + 1
        // 为啥 dp 数组初始化为 amount + 1 呢? 
        // 因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷
        Arrays.fill(dp, amount + 1);

        // base case
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                // 子问题无解，跳过
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

股票问题

num[i] 表示第 i 天的股票价格， 设计一个算法(交易策略) ，计算你能获得的最大收益，你最多可以完成 k 笔交易；

比如： [3,2,6,5,1,3] k=1 , 第2天买入 2块钱， 第3天卖出 6块，利润 6-2 = 4块 是最大利润 k= 2 (可以交易2次) , [2,6] + [1,3] 是最大利润

动态规划思路如下：

  • 状态定义：
  • 状态转移：
  • 状态压缩：

接雨水问题

num[i]表示柱子高度，计算下雨之后最多能接多少雨水

位置i能装多少？ 位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，我们分别称这两个柱子高度为 l_max 和 r_max；位置 i 最大的水柱高度就是 min(l_max, r_max)

思路：

  • 暴力解法
  • 备忘录解法
  • 双指针解法