(1条消息) 爬楼梯,有多少种方式到楼顶?

01、概念讲解

关于动态规划的资料很多,官方的定义是指把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。概念中的各阶段之间的关系,其实指的就是状态转移方程。很多人觉得DP难(下文统称动态规划为DP),根本原因是因为DP跟一些固定形式的算法不同(比如DFS、二分法、KMP),它没有实际的步骤规定第一步、第二步来做什么,所以准确来说,DP其实是一种解决问题的思想

这种思想的本质是:一个规模比较大的问题(可以用两三个参数表示的问题),可以通过若干规模较小的问题的结果来得到的(通常会寻求到一些特殊的计算逻辑,如求最值等),如下图所示,一个大规模的问题由若干个子问题组成。

那么我们应该如何通过子问题去得到大规模问题呢?这就用到了状态转移方程(上面有介绍状态转移方程哦,不懂的请往上翻哦),我们一般看到的状态转移方程,基本都是这样:

opt :指代特殊的计算逻辑,通常为 max or min。i,j,k 都是在定义DP方程中用到的参数。dp[i] = opt(dp[i-1])+1dp[i][j] = w(i,j,k) + opt(dp[i-1][k])dp[i][j] = opt(dp[i-1][j] + xi, dp[i][j-1] + yj, ...)

每一个状态转移方程,多少都有一些细微的差别。这个其实很容易理解,世间的关系多了去了,不可能抽象出完全可以套用的公式。所以我个人其实不建议去死记硬背各种类型的状态转移方程。但是DP的题型真的就完全无法掌握,无法归类进行分析吗?我认为不是的。在本系列中,我将由简入深为大家讲解动态规划这个主题。

02、题目分析

我们先看一道最简单的DP题目,熟悉DP的概念:

第70题:爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? **注意:**给定 n 是一个正整数。

示例 1:

输入: 2   输出: 2  解释: 有两种方法可以爬到楼顶。1.  1 阶 + 1 阶2.  2 阶

示例 2:

输入: 3   输出: 3  解释: 有三种方法可以爬到楼顶。1.  1 阶 + 1 阶 + 1 阶2.  1 阶 + 2 阶3.  2 阶 + 1 阶

03 、图解分析

通过分析我们可以明确,该题可以被分解为一些包含最优子结构的子问题,即它的最优解可以从其子问题的最优解来有效地构建。满足“将大问题分解为若干个规模较小的问题”的条件。所我们令 dp[n] 表示能到达第 n 阶的方法总数,可以得到如下状态转移方程:

dp[n]=dp[n-1]+dp[n-2]

  • 上 1 阶台阶:有1种方式。

  • 上 2 阶台阶:有1+1和2两种方式。

  • 上 3 阶台阶:到达第3阶的方法总数就是到第1阶和第2阶的方法数之和。

  • 上 n 阶台阶,到达第n阶的方法总数就是到第 (n-1) 阶和第 (n-2) 阶的方法数之和。

04、GO语言示例

根据以上分析,可以得到代码如下,go:

func climbStairs(n int) int {if n == 1 {return 1}dp := make([]int, n+1)dp[1] = 1dp[2] = 2for i := 3; i <= n; i++ {dp[i] = dp[i-1] + dp[i-2]}return dp[n]}

java:

class Solution {    public int climbStairs(int n) {        if (n == 1) {            return 1;        }        int[] dp = new int[n+1];        dp[1] = 1;        dp[2] = 2;        for(int i = 3; i <= n; i++ ) {            dp[i] = dp[i-1] + dp[i-2];        }        return dp[n];           }}

我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。

(0)

相关推荐

  • 动态规划之武林秘籍

    听到 动态规划 这个响亮的大名你可能已经望而却步,那是因为这个响亮的名字真的真的很具有迷惑性,不像递归.回溯和贪心等等算法一样,其文即其意,而动态规划则不同,很容易望文生义,真可谓害人不浅,今天我就带 ...

  • 动态规划详解

    这篇文章是我们号半年前一篇 200 多赞赏的成名之作 动态规划详解 的进阶版.由于账号迁移的原因,旧文无法被搜索到,所以我润色了本文,并添加了更多干货内容,希望本文成为解决动态规划的一部「指导方针」. ...

  • 剑指 Offer 14- I. 剪绳子

    我服了.动态规划杀我. 可以说一说解决动态规划的思路(只做了两三道就总结了emmm) 1.识别动态规划问题 --重叠子问题:大问题可以分为一个个子问题.和分治策略分割的子问题不同(分治问题的子问题是相 ...

  • 动态规划之状态转移方程-NOIP提高组历年高频考点(4)

    通过分析NOIP2011-2018年提高组的试题我们就会发现,考察最多的考点前三名就是模拟,动态规划和贪心算法.今天我们来介绍一下动态规划常用的状态转移方程. 动态规划之状态压缩DP-NOIP提高组历 ...

  • 动态规划答疑篇

    ----------- 这篇文章就给你讲明白两个问题: 1.到底什么才叫「最优子结构」,和动态规划什么关系. 2.为什么动态规划遍历 dp 数组的方式五花八门,有的正着遍历,有的倒着遍历,有的斜着遍历 ...

  • 狂刷100道题,我是怎么向5岁侄女解释动态规划的? | 掘金年度征文

    我膨胀了,相信看了这个标题的同学,肯定忍不住破口大骂,什么瓜皮哦,dynamic programming这么简单吗,在我的印象里,尼玛动态规划是最难的. 背景 侄女5岁现在开始学习加减法了,每次做数学 ...

  • 经典动态规划:0-1 背包问题

    前言 经过前面三篇动态规划文章的介绍,相信大家对动态规划.分治.贪心有了充分的理解,对动态规划的 3 个核心问题.其本质也有了了解. 纸上得来终觉浅,绝知此事要躬行. 那么今天开始我们来聊聊具体的那些 ...

  • Python |石子游戏的最大得分

    引言 力扣(LeetCode),未来不止于此! 问题描述 你正在玩一个单人游戏,面前放置着大小分别为 a.b和c的三堆石子. 每回合你都要从两个不同的非空堆 中取出一颗石子,并在得分上加 1 分.当存 ...

  • 图解 | 你管这破玩意叫动态规划

    低并发编程,周一很颓废,周四很硬核 1 小宇:闪客,我最近在研究动态规划,但感觉就是想不明白,你能不能给我讲讲呀? 闪客:没问题,这个我擅长,你先说说提到动态规划,你最先想到的是什么? 小宇:就什么子 ...

  • 欣赏《戴珍珠耳环的少女》有多少种方式?

    △ 维米尔(Johannes Vermeer,1632-1675) 与哈尔斯.伦勃朗合称为荷兰三大画家 代表作:<戴珍珠耳环的少女> 现收藏于荷兰海牙莫瑞泰斯皇家美术馆 蒙娜丽莎以富含深意 ...

  • (7条消息) Qt的5种常用布局搭建

    Qt--中心窗口setCentralWidget http://blog.csdn.net/qter_wd007/article/details/7028920 Qt程序中的主窗口通常具有一个中心窗口 ...

  • 【科普】普洱茶的拼配到底有多少种方式?来~

    拼配是茶叶精制加工厂毛茶验收定级,精制加工,半成品拼配三大环节之一,调剂在拼配之时是必不可少的,那么普洱茶拼配的调剂到底有哪些呢?今天我们就一起来学习一下! 半成品原料的季别调剂 普洱茶原料来自春.夏 ...

  • 社工筹款可以有多少种方式?| 督督导导(社工客廳)第18期精彩回顾

    有没有等着急? :本期嘉宾 集颜值与才华与一身的社工女神们!!! 关键词: 中华女子学院  ·南京大学MSW 项目总监  · 营销总监 与众不同的是,她们都有企业工作的背景, 最后又回归社工行业, 来 ...

  • 记忆一个人,有多少种方式?

    文字仅关联读书时的感悟和行走中的思考. 只需真正喜欢读书和行走的人关注. <黄色基督>,高更.图片来源:网络 一代过去,一代又来.大地却永远长存. --<圣经> 1/ 5月8日 ...

  • (1条消息) 注册JNI函数的两种方式

    前言 前面介绍过如何实现在Android Studio中制作我们自己的so库,相信大家看过之后基本清楚如何在Android studio创建JNI函数并最终编译成不同cpu架构的so库,但那篇文章介绍 ...

  • (5条消息) C#中创建线程的四种方式

    文章目录 前言 利用委托开启线程 步骤 传递参数 获得函数结果 利用Thread类直接开启线程 传递参数 线程的优先级 线程的状态 注意事项 利用线程池开启线程 利用任务开启线程 连续任务 任务层次结 ...

  • (8条消息) Python常用的几种包(库、模块)安装方式

    这里整理一下常见的几种包安装方式 1.pip install package_name 使用pip工具安装,此方法比较常用,方便快捷,自动下载安装包到当前python环境,如果需要指定下载安装某个版本 ...

  • 干货分享丨让你投资轻松赔钱的3种方式,希望你1条也别遇上

    昨天写的<干货分享丨让你毕生积蓄打水漂的3种方法!>看到几个朋友都有收藏评论,加上前天的<让毕生积蓄打水漂的4种方法!>上面7种办法完好任意一种,相信让你毕生积蓄都变成0也不是 ...