21

详解三道一维的动态规划算法题

 5 years ago
source link: http://mp.weixin.qq.com/s?__biz=MzIzMTE1ODkyNQ%3D%3D&%3Bmid=2649412348&%3Bidx=1&%3Bsn=55fa1f0c701f763d1bad45b5c2ddfded
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

来源： 知乎

作者： 单金折

前阵子写了两篇动态规划的文章

后面说要给大家讲解一些案例，不过一直没讲，由于前阵子手受伤了导致手不能运动，一直没给大家写文章，所以呢，我就找一些感觉还不错的文章供大家消费。

例1: 打家劫舍

动态规划思考步骤：

1、原问题：

在一条直线上，有n个房屋，每个房屋中有数量不等的财宝，有一个盗 贼希望从房屋中盗取财宝，由于房屋中有报警器，如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问在不触发报警器的前提下，最多可获取多少财宝？例如 [5，2，6，3，1，7]，则选择5，6，7

来源于LeetCode 198. House Robber

2 、子问题：

（1）、只考虑前两个房间时，谁大选谁

（2）、考虑第三个房间

  • 如果偷第三个房间，则意味着第二个房间不投，也就是第三个房间值 + 第一个房间的宝藏数量

  • 如果不偷第三个房间，则宝藏数量等于前两个房间宝藏数量

3、确认状态：

int [] nums; // 各个房间的宝藏数

int [] flags = new int [n]; // 记录各个房间有没有被偷，若flag = 0 则没偷， flag = 1 则偷了。

int [] dp = new int [n]; // dp[i]表示前i个房间偷到的最大宝藏数

4、初始状态：

第一个房间：

  • Condistion 1 ：dp[0] = nums[0] ; flags[0] = 1;

  • Condistion 2 ：dp[0] = 0; flags[0] = 0;

第二个房间：

  • Condistion 1 ：when flags[1] = 1; dp[1] = nums[1];

  • Condistion 2 ：whenflags[1] = 0; dp[1] = dp[0];

  • 选 Condistion 1 还是 Condistion 2呢？比较 两种情况下dp[1]的大小

    推广到前i个房间: (i>=2)

  • when flags[i] = 1, dp[i] = nums[i] + dp[i-2]

  • when flags[i] = 0; dp[i] = dp[i-1]

5、状态转移方程：

dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i = 2;i<n;i++)
    dp[i] = max(nums[i] + dp[i-2],dp[i-1])

6、代码实现

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0)
            return 0;
        int [] dp = new int[nums.length];
        dp[0] = nums[0];
        // 每次做数组判定时都需要做数组边界判定，防止越界
        if(nums.length < 2)
            return nums[0];
        dp[1] = (nums[0]>nums[1]) ? nums[0] : nums[1];
        for(int i = 2;i<nums.length;i++)
            dp[i] = ((nums[i] + dp[i-2]) > dp[i-1]) ? (nums[i]+dp[i-2]) : dp[i-1];
        return dp[nums.length-1];
    }
}

例2:最大子段和

动态规划思考步骤：

1、原问题

给定一个数组，求这个数组的连续子数组中，最大的那一段的和。

如数组[-2,1,-3,4,-1,2,1,-5,4] 的子段为：[-2,1]、[1,-3,4,-1]、[4,-1,2,1]、…、[-2,1,-3,4,-1,2,1,-5,4]，和最大的是[4,1,2,1]，为6。

示例：
Input: int [] nums = [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

来源于LeetCode 53. Maximum Subarray

2、子问题

  • 只考虑第一个元素，则最大子段和为其本身 DP[0] = nums[0]

  • 考虑前两个元素，最大子段和为 nums[0],num[1]以及 nums[0] + num[1] 中最大值 设为DP[1]

  • 考虑前三个元素，如何求其最大子段和？还是分为两种情况讨论，第三个元素在最后的字串内吗？

    • 若第三个元素也包含在最后的字串内，则DP[2] = Max(DP[1]+nums[2] , nums[2])

3、确认状态

DP[i] 为 以nums[i]结尾的子段的最大最短和

例如 DP[1]则为以nums[1]结尾的最大字段和

4、初始状态

dp[0] = nums[0]

dp[1] = max(dp[0]+nums[1] , nums[1])

5、状态转移方程：

dp[i] = max(dp[i-1]+nums[i],nums[i])

6、解题代码：

public class lc53_MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0)
            return 0;
        int [] dp = new int[len];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i<len;i++){
            dp[i] = (dp[i-1]+nums[i] > nums[i]) ? dp[i-1]+nums[i] : nums[i];
            if (dp[i]>max)
                max = dp[i];
        }
        return max;
    }
}

例3：找零钱

已知不同面值的钞票，求如 何用最少数量的钞票组成某个金额，求可 以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额， 则返回-1。

示例：
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Input: coins = [2], amount = 3
Output: -1

来源于LeetCode 322. Coin Change

动态规划解题步骤：

将原问题拆分成子问题

  • 已知什么？显而易见，钞票的金额都只需要其本身1张即可

  • 如何在已知钞票的情况下构造出 金额X需要的最少钞票组合

确认状态

DP[0] - DP[amount] 表示构造金额amount需要的最小钞票数

确认边界状态（初始条件）

  • DP[coin] = 1 其他的都未知初始值设为 -1

  • 例如coins = [1, 2, 5], amount = 11 已知 dp[1]、dp[2]、dp[5] =1

  • 现在已知 DP[coin] 需要求出每一个DP[amount]

状态转移方程

dp[i] = min(dp[i-1], dp[i-2], dp[i-5]) + 1

解题代码：（java）

    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        if (len == 0 || amount<0)
            return -1;
        if (amount==0)
            return 0;
        int [] dp = new int[amount+1];
        for (int i = 0; i <= amount; i++){
            dp[i] = -1;
        }
        for (int i = 0; i< len;i++){
            if(coins[i] == amount)
                return 1;
            if(coins[i] < amount)
                dp[coins[i]] = 1;
        }
        // State Transfer Function
        for(int i = 1; i <= amount;i++){
            for (int j = 0; j < len; j++){
                if (i - coins[j] >= 0 && dp[i - coins[j]] != -1){
                    if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1){
                        dp[i] = dp[i - coins[j]] + 1;
                    }
                }
            }
        }
        return dp[amount];
    }

总结

今天实例了三道一维的题，属于 leetcode 中 medium 级别的题吧，大家也可以根据题号去搜索练练手。

zuUnyaE.jpg!web


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK