专栏首页小浩算法《剑指offer》第25天:最简单的动态规划

《剑指offer》第25天:最简单的动态规划

01、动态规划概念讲解

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

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

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

opt :指代特殊的计算逻辑,通常为 max or min。

i,j,k 都是在定义DP方程中用到的参数。

dp[i] = opt(dp[i-1])+1

dp[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语言:

func climbStairs(n int) int {
 if n == 1 {
  return 1
 }
 dp := make([]int, n+1)
 dp[1] = 1
 dp[2] = 2
 for 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];       
    }
}

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

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

原始发表时间:2020-09-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:动态规划系列 第一讲

    讲解动态规划的资料很多,官方的定义是指把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。概念中的各阶段之间的关系,其实指的就是状态转移...

    程序员小浩
  • 漫画:BAT必考题目 (如何压缩状态完成不同路径题目)

    不同路径:一个机器人位于一个 m x n 网格的左上角,起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,在下...

    程序员小浩
  • 《剑指offer》第26天:最大子序和

    首先我们分析题目,一个连续子数组一定要以一个数作为结尾,那么我们可以将状态定义成如下:

    程序员小浩
  • 一天一大 leet(最长有效括号)难度:困难-Day20200704

    给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

    前端小书童
  • Python|利用代码求三角形最小路径和

    题目:给定一个三角形,每一步只能移动到下一行中相邻的结点上,求出自顶向下的最小路径和。

    算法与编程之美
  • 利用python代码求三角形最小路径和

    哈喽!同学们,今天和大家分享一下,利用Python代码求三角形最小路径和!给定一个三角形,每一步只能移动到下一行中相邻的结点上,求出自顶向下的最小路径和。

    小小科
  • LintCode 125. 背包问题 II(DP)

    有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小 数组 V 表示每个物品的价值.

    Michael阿明
  • Leetcode Golang 115. Distinct Subsequences.go

    dp dp[i][j]表示构成i长度的t,用到j长度的s,结果等于种类 转移方程: 如果t[i]==s[j],dp[i][j]=dp[i-1][j-1]+...

    anakinsun
  • LeetCode 801. 使序列递增的最小交换次数(动态规划)

    我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。

    Michael阿明
  • [Leetcode][python]Triangle/三角形最小路径和

    参考:https://shenjie1993.gitbooks.io/leetcode-python/120%20Triangle.html 将一个二维数组...

    后端技术漫谈

扫码关注云+社区

领取腾讯云代金券