浅谈动态规划Ⅲ

编程算法

字数统计: 2.8k阅读时长: 12 min

 2020/07/20   Share

前言

最近准备秋招感觉自己还是蛮菜的，啥都不会。但学习还是得继续，偶尔趁着休息时间来写写文章。这篇大概是最后一篇整理动态规划题目，感觉整理多了也没用，只有自己去理解才真正有用。话不多说，开始正文。

实践

地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。为了尽快到达公主，骑士决定每次只向右或向下移动一步。

来自leetcode 174题
这道题目很像我在浅谈动态规划Ⅰ中所讲的入门题目，即最小路径权重问题。但如果我们从左上角开始进行动态规划，我们只能知道起点到终点的所需要最小血量，但是并不能保证当到达每个点时的血量不低于1。所以我们采用反向dp，即从右下角往起点进行动态规划。
我们令dp[i][j]为坐标(i,j)到终点所需要的最小血量。那么我们的最终答案就是dp[0][0]。
接下来是动态转移方程。我们先考虑dp[m-1][n-1]，也就是终点到终点需要的血量，很容易想到，应该是max(1,1-dungeon[m-1][n-1])，因为血量不能低于1，如果有怪物的话需要怪物血量加上1，两者取大值。
那其他点呢，很简单，我们需要的最少血量，而且每次只能从右或者从下走一格，因为我们是反向dp，(i,j)坐标获取的状态应该是(i+1,j)和(i,j+1)，所以对应的应该是dp[i+1][j]和dp[i][j+1]的较小值，再减去当前坐标的值，与1对比取大值，即dp[i][j] = max(1,min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j])。
在dp数组空间的选择上，有两个选择，一种是m*n，另一种是 (m+1)*(n+1)，这两个选择其实是对边界的处理有差别。
如果采用m*n的数组空间，那么我就必须对dp[m-1][n-1]，即终点位置进行独立地初始化，并且需要对dp[i][n-1]与dp[m-1][j]这一行一列进行独立赋值，避免数组越界。
而采用(m+1)*(n+1)的空间，只需要把外围空间赋值为无穷大，并对终点的下方和右方赋值为1，便可实现使用一个状态转移方程完成全部计算。

//m*n
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon == null || dungeon.length == 0 || dungeon[0].length == 0){
            return 0;
        }
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];
        
        dp[m-1][n-1] = Math.max(1,1-dungeon[m-1][n-1]);
        
        for (int i = m-2;i > -1;i--){
            dp[i][n-1] = Math.max(1,dp[i+1][n-1] - dungeon[i][n-1]);
        }

        for (int i = n-2;i >-1;i--){
            dp[m-1][i] = Math.max(1,dp[m-1][i+1] - dungeon[m-1][i]);
        }

        for (int i = m-1;i > -1;i--){
            for (int j = n-1;j > -1 ; j--){
                dp[i][j] = Math.max(1,Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j]);
            }

        }
        return dp[0][0];

    }
}

//(m+1)*(n+1)空间
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon == null || dungeon.length == 0 || dungeon[0].length == 0){
            return 0;
        }
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = m-1;i > -1;i--){
            for (int j = n-1;j > -1 ; j--){
                dp[i][j] = Math.max(1,Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j]);
            }

        }
        return dp[0][0];
    }
}

但其实只是因为第二种方法更简单些，并且不用额外初始化，时间复杂度是一样的。如果要更进一步，因为dp[i][j]状态只与dp[i+1][j]与dp[i][j+1]有关，所以我们可以使用滚动数组方法来降低空间复杂度，这里就不再展开。

最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。火车票有三种不同的销售方式：
一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

来自leetcode 983题
思路还是比较简单的，先定义状态，很显然，这是个一维dp问题，所有我们定义dp[i]为第i天所需要花费的费用。

如果当天没有旅游，那么dp[i] = dp[i-1]

如果当前是旅游的，那么我们应该从三种方案中选择最小花费，也就是dp[i] = min(dp[i-1]+costs[0],dp[i-7]+cost[1],dp[i-30]+costs[2]).这里需要注意数组越界问题。

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int m = days[n-1] + 1;
        int[] dp = new int[m];
        int day_index = 0;
        for (int i = 1;i<m;i++){
            if (i != days[day_index]){
                dp[i] = dp[i-1];
                continue;
            }else{
                day_index++;
                dp[i] = min(dp[Math.max(0,i-1)]+costs[0],dp[Math.max(0,i-7)]+costs[1],dp[Math.max(0,i-30)] + costs[2]);
            }
        }
        return dp[m-1];
    }
    private int min(int a,int b,int c){
        return Math.min(Math.min(a,b),c);
    }
}

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

来自leetcode 121题
这道题目其实只要一次遍历过程中维护一个最小值就可以解决。如果用动态规划的解法呢？
买卖股票，无非就是两种状态，一种买入，一种卖出，两种状态我们定义二维数组dp，先定义买入收益为dp[0](注意这里收益是负的)，卖出的收益为dp[1]，买入的成本应该是dp[0][i] = max(dp[0][i-1],-prices[i])，因为是负数，所以用max。而卖出的收益应该为第i-1天卖出的收益与i-1天时买入收益加上当天股价，取两者较大者，即dp[1][i] = max(dp[1][i-1],dp[0][i-1]+prices[0])

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0){
            return 0;
        }

        int n = prices.length;
        int[][] dp = new int[2][n];

        dp[0][0] = -prices[0];
        dp[1][0] = 0;
        for (int i = 1;i<n;i++){
            dp[1][i] = Math.max(dp[1][i-1],dp[0][i-1]+prices[i]);
            dp[0][i] = Math.max(dp[0][i-1],-prices[i]);
        }
        return dp[1][n-1]; // 最大收益只在卖出状态中产生。
        // return Math.max(dp[0][n-1],dp[1][n-1]);
    }
}

上面代码中第一维是状态，第二维是时间。
我们可以更换一下以更好理解下一道题目。dp[i]代表第i天，dp[i][0]代表第i天卖出的收益(即不持股)，而dp[i][1]代表第i天买入的收益(即持股)。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        
        for(int i=1;i<n;++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[n-1][0];
    }
}

买卖股票的最佳时机Ⅱ

来自leetcode 122题
这道题相比上一道，多了一个可以多次买卖的条件。因此买入的状态可以由卖出的状态来进行转移，即持股的状态可以由不持股的状态转移而来。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        
        for(int i=1;i<n;++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[n-1][0];
    }
}

买卖股票的最佳时机含冻结期

这道题比上面那道多了一个冻结期，即卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)，并且不限制买卖次数。
来自leetcode 309题
这道题由于多了冻结期的概念，所以应该比上一道题多一种状态，dp[i]依旧表示第i天的收益，而第二维有三个状态，分别为不持股，持股，冻结期。然后分析状态转移方程，首先不持股是由昨天不持股和昨天持股今天买股两种状态转移而来，而持股的状态则是由昨天持股与昨天冻结，今天买股两个状态转移而来。
翻译成代码就是

public class Solution {

    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }

        int[][] dp = new int[n][3];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for (int i = 1; i < n; 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][2] - prices[i]);
            dp[i][2] = dp[i - 1][0];
        }
        return Math.max(dp[n - 1][0], dp[n - 1][2]);
    }
}

总结

以上就是本次整理的几道题目，我个人感觉股票问题是十分经典的，并且层层递进，还有几道股票题目没有整理出来，如果有闲下来的时间，下次再整理吧。整理题目也算是一种复习吧，感觉对动态规划的理解又加深不少。

原文作者：Zer0e

原文链接：https://re0.top/2020/07/20/dp3/

发表日期：七月 20日 2020, 4:10:00 下午

更新日期：July 23rd 2020, 11:21:11 pm

Next Post

浅谈Java线程池
Previous Post

浅谈数据库主从复制

CATALOG

1. 前言
2. 实践
3. 总结

