专栏首页苦逼的码农详解三道一维的动态规划算法题

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

来源:知乎(已获得授权)

作者:单金折

例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];
    }

本文分享自微信公众号 - 苦逼的码农(di201805),作者:单金折

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • TwoSum 相关问题思路总结

    TwoSum 作为 LeetCode 的第一题存在,想必大家应该对其并不陌生。如果仅仅是看这道题目本身,并不难,思想也特别的简单。

    帅地
  • 详解 leetcode 221 题:最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    帅地
  • 【leetcode】16. 最接近的三数之和

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假...

    帅地
  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • LintCode 解码方法题目分析代码

    样例 给你的消息为12,有两种方式解码 AB(12) 或者 L(12). 所以返回 2

    desperate633
  • 算法细节系列(21):贪心有理?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Golang Leetcode 334. Increasing Triplet Subsequence.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89068924

    anakinsun
  • 初级算法-动态规划

    动态规划主要是解一些递归问题,也就是将递归写成非递归方式,因为编辑器无法正确对待递归,递归方法会导致很多计算结果被重复计算,比如菲波那切数列。

    方丈的寺院
  • 【leetcode刷题】T165-最长上升子序列

    https://leetcode-cn.com/problems/longest-increasing-subsequence/

    木又AI帮
  • 每日算法系列【LeetCode 312】戳气球

    有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

    godweiyang

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动