1.1. 基本结构

动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decision process)中最优化的数学方法。

  • 起源:在研究多阶段决策过程(multi-step decision process)的优化问题时,提出的最优性原理(principle of optimality),把多阶段过程转化为单阶段问题,逐个求解。
  • 应用领域:经济管理、生产调度、工程技术和最优控制。
  • 局限:主要是用于求解“分阶段”的动态过程的优化问题。
  • 经典问题:背包问题
  • 比较:
    • 贪婪:永远局部最优
    • 递归:重复计算
    • DP:记录局部最优子结构/多种记录值

1.1.1. 基本概念

  • 阶段step:它是对整个过程的划分,通常会根据时间或者空间顺序进行分阶段。
  • 状态state:它表示每个阶段开始时过程所处的自然状况,它描述了过程的特征并且无后效性。
    • 无后效应:与之前的状态无关。
    • 状体变量state variable:用于描述状态的变量。
  • 决策decision:当一个阶段状态确定后,可以作出各种选择从而演变到下一阶段的某种状态,称为决策。
  • 策略 policy:决策组成的序列称为策略。
  • 状态转移方程 equation of state transition :用于描述某阶段的状态和决策与下阶段状态的关系。

1.1.2. 基本思想-- 多阶段决策。

1.1.3. 实现步骤

  1. 递推 / 递归+记忆性
  2. 动态规划:分治+最优子结构(每次都淘汰掉次优的状态。例如step(n) = Max(step(n-1)+n,step(n-2)),淘汰了小的那一个)

1.1.4. 递归模板

public void recur(int level, int param) { 
  // terminator 
  if (level > MAX_LEVEL) { 
    // process result 
    return; 
  } 
  // process current logic 
  process(level, param); 
  // drill down 
  recur( level: level + 1, newParam); 
  // restore current status 
}

1.2. 常见面试题

1.2.1. 53. 最大子序和

public int maxSubArray(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    int[] ans = new int[nums.length]; // 定义状态
    ans[0] = nums[0];
    int max = ans[0];// 初始值
    for (int i = 1; i < nums.length; i++) {//更新状态
        ans[i] = Math.max(nums[i], ans[i - 1] + nums[i]);
        max = Math.max(max, ans[i]);
    }
    return max;
}

1.2.2. 70. 爬楼梯

当前楼层的种类数,等于前一步和前两步的总和。因为每次只能走一步或者两步。

// 1. 递归
public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}
// 2. 递归+记忆性
Map<Integer, Integer> map = new HashMap<>();
public int climbStairs(int n) {
    if (n == 1) {
        map.put(1, 1);
        return 1;
    } else if (n == 2) {
        map.put(2, 2);
        return 2;
    }
    int step1 = map.containsKey(n - 1) ? map.get(n - 1) : climbStairs(n - 1);
    int step2 = map.containsKey(n - 2) ? map.get(n - 2) : climbStairs(n - 2);
    map.put(n, step2 + step1);
    return step2 + step1;
}
// 3. 递推
public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        // 0,1 分别表示第一级和第二级
        int[] result = new int[n];
        result[0] = 1;
        result[1] = 2;
        for (int i = 2; i < n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n-1];
    }
}

1.2.3. 72. 编辑距离

参考于这个文章

public int minDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();
    // 如果有一个等于0,则是n+m(将另一个完全替换)。
    if (n * m == 0) {
        return n + m;
    }
    int[][] arr = new int[n + 1][m + 1];
    for (int i = 0; i < n + 1; i++) {
        arr[i][0] = i;
    }
    for (int i = 0; i < m + 1; i++) {
        arr[0][i] = i;
    }
    // 假设现在是 HOR与RO比较, left表示HOR与R的距离,down表示HO与RO的距离,slash表示HO与R的距离。
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            int left = arr[i - 1][j] + 1;
            int down = arr[i][j - 1] + 1;
            int slash = arr[i - 1][j - 1];
            if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                slash += 1;
            }
            arr[i][j] = Math.min(left, Math.min(down, slash));
        }
    }
    return arr[n][m];
}

1.2.4. 120. 三角形最小路径和

每个数都等于当前数加上,上一行可以加的最小值的数。

public int minimumTotal(List<List<Integer>> triangle) {
    int len = (triangle.size() + 1) * triangle.size() / 2;
    int[] ans = new int[len];
    ans[0] = triangle.get(0).get(0);
    int k = 1;
    for (int i = 1; i < triangle.size(); i++) {
        List<Integer> list = triangle.get(i);
        int size = list.size();
        for (int j = 0; j < size; j++, k++) {
            // 先处理最左边和最右边
            if (j == 0) {
                // 处理最左侧的,减去上一行的长度
                ans[k] = ans[k - (size - 1)] + list.get(j);
            } else if (j == size - 1) {
                // 处理最右侧的,减去本行的长度
                ans[k] = ans[k - size] + list.get(j);
            } else {
                ans[k] = Math.min(ans[k - size], ans[k - size + 1]) + list.get(j);
            }
        }
    }
    // 找到最小值
    int min = Integer.MAX_VALUE;
    for (int i = len-triangle.size(); i < len; i++) {
        min =Math.min(ans[i],min);
    }
    return min;
}

1.2.5. 152. 乘积最大子序列

1.2.6. 198. 打家劫舍

两层循环

public int rob(int[] nums) {
    if (nums.length == 0) {
        return 0;
    } else if (nums.length == 1) {
        return nums[0];
    } else if (nums.length == 2) {
        return Math.max(nums[0], nums[1]);
    }
    int[] ans = new int[nums.length];
    ans[0] = nums[0];
    ans[1] = nums[1];
    for (int i = 2; i < nums.length; i++) {
        int max = ans[i - 1];
        for (int j = 0; j < i - 1; j++) {
            max = Math.max(nums[i] + ans[j], max);
        }
        ans[i] = max;
    }
    return ans[nums.length - 1];
}

动态规划

public int rob(int[] nums) {
    int prevMax = 0; // 之前最大
    int currMax = 0; // 现在最大
    for (int num : nums) {
        int temp = currMax; // 记录现在最大
        currMax = Math.max(prevMax + num, currMax); // 找到最大
        prevMax = temp; // 移动
    }
    return currMax;
}

1.2.7. 300. 最长上升子序列

1.2.8. 309. 最佳买卖股票时机含冷冻期

1.2.9. 322. 零钱兑换

// 递归
public int coinChange(int[] coins, int amount) {
    // 终结条件
    if (amount == 0) {
        return 0;
    }
    // 初始化结果,进行操作
    int ans = Integer.MAX_VALUE; 
    for (int coin : coins) {
        if (amount - coin < 0) {
            continue;
        } else {
            int sub = coinChange(coins, amount - coin);
            if (sub == -1) {
                continue;
            } else {
                ans = Math.min(ans, sub + 1);
            }
        }
    }
    return ans == Integer.MAX_VALUE ? -1 : ans;
}
// 2.递推
public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int[] res = new int[amount+1];
    for (int i = 1; i < res.length; i++) {
        int cost = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (i - coin >= 0 && res[i - coin] != Integer.MAX_VALUE) {
                cost = Math.min(res[i - coin] + 1, cost);
            }
        }
        res[i] = cost;
    }
    return res[amount]==Integer.MAX_VALUE?-1:res[amount];
}

1.2.10. 714. 买卖股票的最佳时机含手续费

1.3. 股票问题

参考这篇文章《一个通用方法团灭 6 道股票问题

  1. 定义状态,dp[i][K][0 or 1]:i表示天数,k表示交易的次数,0表示未持有,1表示持有。
  2. 初始状态:这里的-1表示开始的前一天。
    • dp[-1][K][0]=0,dp[-1][k][1]=-inf;刚开始初始状态不允许交易,不持有利润为0;持有是负无穷(不允许)。
    • dp[i-1][0][0]=0,dp[i-1][0][1]=-inf;当交易次数没了。不持有的利润为0,持有为负无穷(不允许)。
  3. 转移方程,分为两个。(在买入时,减少交易次数)
    • i天不持有:dp[i][k][0]=MAX(dp[i-1][k][0],dp[i-1][k][1]+price[i]);前一天可以有两种状态:第一种前一天也不持有;第二种是前一天持有,今天卖出。
    • i天持有:dp[i][k][1]=MAX(dp[i-1][k][1],dp[i-1][k-1][0]-price[i]),前一天可以有两种状态:第一种前一天也持有;第二种是前一天不持有,今天选择买(所以k-1)。
  4. 最后 return 的值,肯定是最后一天不持有的状态,要不然就亏了。

再具体的细节,可以参考上面这个文章。

1.3.1. 121. 买卖股票的最佳时机(仅一次交易)

  • 初始状态:dp[0][0]=0,dp[0][1]=-price[0]
  • 不持有:dp[i][1][0]=MAX(dp[i-1][1][0],dp[i-1][1][1]+price[i])
  • 持有:dp[i][1][1]=MAX(dp[i-1][1][1],dp[i-1][0][0]-price[i])=MAX(dp[i-1][1][1],-price[i])
public int maxProfit(int[] prices) {
    if (prices.length < 2) {
        return 0;
    }
    // 状态矩阵
    int[][] dp = new int[prices.length][2];
    // 初始状态
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    // 遍历
    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
    }
    return dp[prices.length - 1][0];
}
// 简便写法
public int maxProfit(int[] prices) {
    int prevHold = 0, prevNotHold = Integer.MIN_VALUE;
    for (int price : prices) {
        // 注意:这里有状态变换。
        //dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        prevHold = Math.max(prevHold, prevNotHold + price);
        //dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        prevNotHold = Math.max(prevNotHold, -price);
    }
    return prevHold;
}

1.3.2. 122. 买卖股票的最佳时机 II(不限交易次数)

k无穷。

  • 初始状态:dp[0][k][0]=0,dp[0][k-1][1]=-price[0]
  • 不持有:dp[i][k][0]=MAX(dp[i-1][k][0],dp[i-1][k][1]+price[i])=MAX(dp[i-1][0],dp[i-1][1]+price[i])
  • 持有:dp[i][k][1]=MAX(dp[i-1][k][1],dp[i-1][k-1][0]-price[i])=MAX(dp[i-1][1],dp[i-1][0]-price[i])
public int maxProfit(int[] prices) {
    if (prices.length < 2) {
        return 0;
    }
    // 状态矩阵
    int[][] dp = new int[prices.length][2];
    // 初始状态
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    // 遍历
    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[prices.length - 1][0];
}

1.3.3. 309. 最佳买卖股票时机含冷冻期(不限次数,但隔一天才能买)

k无穷

  • 初始状态:dp[0][0]=0,dp[0][1]=-price[0]
  • 不持有:dp[i][0]=MAX(dp[i-1][0],dp[i-1][1]+price[i])
  • 持有:dp[i][1]=MAX(dp[i-1][1],dp[i-2][0]-price[i])
public int maxProfit(int[] prices) {
    if (prices.length < 2) {
        return 0;
    }
    // 状态矩阵
    int[][] dp = new int[prices.length][2];
    // 初始状态
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
    dp[1][1] = Math.max(dp[0][1],  - prices[1]);
    // 遍历
    for (int i = 2; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
    }
    return dp[prices.length - 1][0];
}

1.3.4. 714. 买卖股票的最佳时机含手续费(不限次数,但要手续费)

  • 初始状态:dp[0][0]=0,dp[0][1]=-price[0]-fee
  • 不持有:dp[i][0]=MAX(dp[i-1][0],dp[i-1][1]+price[i])
  • 持有:dp[i][1]=MAX(dp[i-1][1],dp[i-1][0]-price[i]-fee)
public int maxProfit(int[] prices, int fee) {
    if (prices.length < 2) {
        return 0;
    }
    // 状态矩阵
    int[][] dp = new int[prices.length][2];
    // 初始状态
    dp[0][0] = 0;
    dp[0][1] = -prices[0] - fee;
    // 遍历
    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
    }
    return dp[prices.length - 1][0];
}

1.3.5. 123. 买卖股票的最佳时机 III

1.3.6. 188. 买卖股票的最佳时机 IV(k次交易)

  • 初始状态:dp[0][k][0]=0,dp[0][k-1][1]=-price[0]
  • 不持有:dp[i][k][0]=MAX(dp[i-1][0],dp[i-1][1]+price[i])
  • 持有:dp[i][k][1]=MAX(dp[i-1][1],dp[i-1][0]-price[i]-fee)

results matching ""

    No results matching ""