专栏首页方丈的寺院初级算法-动态规划

初级算法-动态规划

摘要

本篇主要介绍动态规划解题思路

概括

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

所以动态规划的解题思路也就是

  1. 列出递归表达式
  2. 将递归方法写成非递归方式

比如菲波那切数列 F(n) = F(n-1) + F(n-2) 使用两个中间变量存储之前的计算结果,就改写成了非递归方式实现,也就是动态规划。

常见的题

leetcode 动态规划题 https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/23/dynamic-programming/

一. 爬楼梯

假设你正在爬楼梯。需要 n 步你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

按照解题方法,写列出递归方程 设定dp[i] 表示走到某个台阶的方法,那么就有递归方程

dp[1] = 1;dp[2] = 2(一次走一步/一次走二步)
dp[3] = dp[1] + dp[2] (从dp[1]中方法中,走2步上来,或者从dp[2]种方法中走1步上来)
dp[n] = dp[n-2] + dp[n-1]

写成非递归方法

public static int climbStairs(int n) {
        if(n < 1) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }
        int dp[] = new int [] {1,2};
        int result = dp[0] + dp[1];
        for (int i = 3; i <= n; i++) {
            result = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = result;
        }
        return result;
    }

二. 最大子序列

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

  1. 列出递归方程 以 nums[-2,1,-3,4,-1,2,1,-5,4] 为例, dp[i]表示遍历到第i个数时,当前最大连续子数组和 dp[1] = -2, dp[2] = Math.max(dp[1] + nums[2],nums[2]),因为要求是连续子数组,所以nums[i]必须接上, 然后再比较历史最大的的连续子数组和这次的最大值

代码如下

 public static int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }
        int result =  Math.max(nums[0]+nums[1],nums[1]);
        int dp = result;
        int max = Math.max(result, nums[0]);
        for (int i = 2; i< nums.length; i++) {
            result = Math.max(dp+nums[i],nums[i]);
            dp = result;
            // 如果比历史的大,就替换
            if (result > max) {
                max = result;
            }
        }
        return max;
    }

三. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额

如 [2,7,9,3,1] 设定dp[i] 是偷i个房屋,所能偷窃到的最高金额,dp[1] = 2, dp[2] = 7, dp[3] = 2+9,Math.max(dp[1] + nums[3], dp[2]) 递归方程

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

非递归方法实现

 public static int rob(int[] nums) {
        if (nums.length ==0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        if (nums.length  ==2) {
            return Math.max(nums[0],nums[1]);
        }

        int dp[] = new int[] {nums[0], Math.max(nums[0], nums[1])};
        int result=0;
        for (int i = 2; i < nums.length; i++) {
            result = Math.max(dp[0] + nums[i], dp[1]);
            dp[0] = dp[1];
            dp[1] = result;
        }
        return result;
    }

本文分享自微信公众号 - 方丈的寺院(gh_c98f244e174d),作者:cnstonefang

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

原始发表时间:2018-07-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Mongo连接分析

    在前面的文章中有分析过关系型数据库的连接,以及连接池的原理。在mongo数据库同样存在,经常看到有网友在问mongo 连接了数据库要不要关,怎么关。内置的数据库...

    方丈的寺院
  • 可落地的DDD的(2)-为什么说MVC工程架构已经过时

    mvc是一种软件设计模式,最早由Trygve Reenskaug在1978年提出,他有效的解决了表示层,控制器层,逻辑层的代码混合在一起的问题,很好的做到了职责...

    方丈的寺院
  • 可落地的DDD(5)-战术设计

    本篇是DDD的战术篇,也就是关于领域事件、领域对象、聚合根、实体、值对象的讨论。也是DDD系列的完结篇。 这一部分在我们团队争论最多的,也有很多月经贴,比如对资...

    方丈的寺院
  • 程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

    Michael阿明
  • 漫画:动态规划系列 第二讲

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

    程序员小浩
  • Golang Leetcode 334. Increasing Triplet Subsequence.go

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

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

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

    用户1147447
  • LintCode 解码方法题目分析代码

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

    desperate633
  • 【leetcode刷题】T165-最长上升子序列

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

    木又AI帮
  • 详解三道一维的动态规划算法题

    在一条直线上,有n个房屋,每个房屋中有数量不等的财宝,有一个盗 贼希望从房屋中盗取财宝,由于房屋中有报警器,如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...

    帅地

扫码关注云+社区

领取腾讯云代金券