动态规划(Dynamic Programming,简称DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时,提出并创立。
动态规划(DP)通过循环做出每一步的最优解从而自底向上的得出对问题的整体最优解;这是它与分支算法的自顶向下求解和与贪心算法寻找局部最优解有本质的区别。
接下来为大家说明三步骤通解动态规划问题
只要掌握这几步必会动态规划任意题型,本文提供多种动态规划题型按此模板解析,话不多说开始例题实战。
问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
输入输出示例,下面给出三次 单独的 各自输入输出;
n=2时有2种跳法,n=7时有21种跳法,n=2时有1种跳法
输入:n = 2 | n = 7 | n = 0
输出:2 | 21 | 1
这里要求跳上n级的台阶有多少种方法,就设dp[n]为跳上n级的台阶的跳法数
动态规划是自底向上解决问题的,所以底部最小单元的初始值是必须明确的,这里我们可以看到上面示例中第三组输入n为0时输出为1(台阶为0级时只有一种跳法);而一级台阶只有一种跳法,两个台阶有两种跳法(1+1/2),三个台阶有三种跳法(1+1+1/1+2/2+1)…
显而易见初始值为n=0和n=1和2时情况
即为dp[0]=1,dp[1]=1,dp[2]=2
上面提到过动态规划通过循环做出每一步的最优解从而自底向上的得出对问题的整体最优解,循环每一步就是依靠每个单元的关系依次推到,由dp[0]靠关系推导到dp[1],由dp[1]推导dp[2]…接下来推导出最终要求的 dp[n] 即为解决问题
这里的n阶台阶方法数推导之间有什么关系?
抛开初始值n=0和n=1,这里稍微思考一下其中关系
台阶数 跳法 跳法数
n=2 11 2 2
n=3 111 12 21 3
n=4 1111 112 121 211 22 5
我们思考一下要跳到一个n级台阶,其最后一步只能在跳一步或两步的方式
这里可以分类
台阶数 最后跳一步的跳法 最后跳两步的跳法 总跳法数
n=2 11 2 1+1=2
n=3 111 21 12 2+1=3
n=4 1111 121 211 112 22 3+2=5
总跳法=最后跳一步的跳法数 + 最后跳两步的跳法数
关系方程就出来了
dp[n]=d[n-1]+d[n-2]
因为本题本质是求斐波那契数列的变体解问题
d[0]=1; d[1]=1; d[2]=2; d[3]=3; d[4]=5
1 1 2 3 5
这里数学基础扎实的读者可以看出从dp[1]开始就是斐波那契数列(2=1+1;3=1+2;5=2+3),继而快速推导出公式
d[n] = d[n-1] + d[n-2] ,这是累计经验更快更准确分析分题,多刷题和思考也能到这样
完成上三步骤后代码解法就很显而易见了,因为解题本质是从题型中分析并确定需要的算法思想,在将其以代码形式表达出来的过程
这里上代码和注释
class Solution {
public int numWays(int n) {
int[] dp = new int[Math.max(n+1, 3)];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i<= n; i++){
dp[i] = (dp[i-1]+dp[i-2]) % 1000000007; //对1000000007取余是题干要求
}
return dp[n];
}
}
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
【示例】
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
本题问题是找出数组和的最大值,那就设最后要返回的最大值为 int max(值为最大和的子数组)
动态规划是自底向上不断循环每一步的最优解来使得全局最优,全局最优解max已经有了
再设出每一步的局部最优解 int dp(值为每次循环中求得的最大数组)
比如要求你三天吃饭用时最大的三餐时间之和max;那么 dp[n] 为你第n天里三顿中用时最长的一顿早/中/晚饭,
max = dp[1] + dp[2] +dp[3]
清楚明白,定义完成
如果是找数组/字符规律那初始值就从最开始的0,1,2套入,然后发现其中特殊的的值
但这里是求已知数组的最大值,而且已经定义好了max和dp,直接将0赋予作为初始值
int dp = nums[0];
int max = nums[0];
清楚明白,已经找好
tip:有小伙伴可能想出想要 子数组和最大,其第一个和最后一个都一定是正数;毕竟开场和结尾可以选择的正数来最大化数组和,但要思考到 [-1] [-1,-2,-3] 这种示例,所以找首尾一定是正数的思维是在这里行不通的。
数组和是由每一个单个的数字环环相扣连接累加而成(理解这句“废话“才能动态规划求最优解)
一个子数组m加上紧接的下一个数字m的值,m+n>n,那铁定把收编到数组里,但如果m+n<n; 那m数组还成了负担,不如重新让数字n替换为新的数组
下举例中m和n都是随机设,主要是表示出这个道理
{3,1,-2}中m为{3+1=4}时,n为-2;m+n>n,所以收编n后新数组m为{3,1,-2}
{-6,2,-1}中m为{-6+2=-4},n为-1;m+n<n,m数组值这么小反而成了累赘,所以令m=n,即m新设为{-1}
将想清楚这种数组的最大构成关系后,就能模拟出关系表达式了
dp = Math.max{ dp + num[i],num[i]}
(第一个max为定义的最大值变量,第二个为 Math.max 是比较并选取两数中较大的一个)
package slaine;
public class test {
public static void main(String[] args) {
int[] nums = {
-2,1,-3,4,-1,2,1,-5,4};
System.out.println(maxSubArray(nums));
}
public static int maxSubArray(int[] nums) {
int dp = nums[0];
int max = nums[0];
for(int i = 1; i < nums.length; i++){
// System.out.println("传入数组第"+i+"个数字是"+nums[i]);
dp = Math.max(dp + nums[i], nums[i]);
// System.out.println("dp选取为"+dp);
max = Math.max(max, dp);
// System.out.println("第"+i+"次循环中最大值为"+max);
System.out.println();
}
return max;
}
}
现在我们开始加速了小伙伴们,冲冲冲,这里选的 “礼物的最大价值” 是刚我们做过的 “连续子数组的最大和” 进阶小变体
很显然本题将 “求连续数组最大和”的一维数组变体为 求二位数组中路径最大值,乍一看有点难搞?不要怕,照样三步骤轻松拆解
注意传入的二维数组为 int[][] [] [] grid;
新建一个n行m列的与输入同格式二维数组 int [] []dp
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
但新建的二维数组dp里要装什么?动动你的小脑袋想想,
【动态规划通过循环做出每一步的最优解从而自底向上的得出对问题的整体最优解】(这句话在本文至少出现三遍…),
那当然显而易见的新建二维数组dp其中 每个元素 是当前循环中的想求的最优解
看不懂上面这句话的笨蛋 在本文 Ctrl+F 搜索 “吃饭” ,背下例子并把【】的话背三十遍
为了更清楚的解释我们建的dp数组要装什么玩意,这里举例(作者S1aine真的殚心竭虑地想给你说明白)
输入二维数组int [] [] grid:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
那么我们新建的二维数组dp就应该是
[
[1,4,5],
[2,9,10],
[6,11,12]
]
回忆一下刚才咱们在 “连续子数组的最大和” 里怎么定义初始值的?直接把初值第0个赋予了max和dp[i]
这里的初值什么? 第一反应是左上角的grid[0] [0] ,将它作为初始值赋予dp[0] [0]没有问题
但是同时要结合题干考虑,题干里明确说了每次只能 “向右 或者 向下” 走,那就明显还需要边界的初始值来约束路径
那边界初始值自然是dp中第0行和第0列了,求第0行和第0列两串初始值
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m]; //左上角初始值
dp[0][0] = grid[0][0];
for(int i = 1; i < n; i++){
//第0列的初始值
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int j = 1; j < m; j++){
//第0行的初始值
dp[0][j] = dp[0][j -1] + grid[0][j];
}
初始值全部找到,下一个步骤
这里直接引用 Krahets 总结好的公式,感谢K佬
class Solution {
public int maxValue(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
dp[0][0] = grid[0][0];
for(int i = 1; i < n; i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int j = 1; j < m; j++){
dp[0][j] = dp[0][j -1] + grid[0][j];
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[n-1][m-1];
}
}
还等着看题解?
都学了这么多了不去练练?
与上题同样是二维数组的动态规划但做了些小变体
点击下方传送门开始手撕
加油哦, ~ ~ ~
文章浏览阅读3.8k次,点赞9次,收藏28次。直接上一个工作中碰到的问题,另外一个系统开启多线程调用我这边的接口,然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法,放到线上后发现确实是可以正常取到结果,但是一旦调用,CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了,类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99
文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效
文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别,这些API绝大多数都被包装到了一个具名和核心模块中了,例如文件操作的 fs 核心模块 ,http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是
文章浏览阅读10w+次,点赞435次,收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件
文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢?1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件
文章浏览阅读867次,点赞2次,收藏2次。docker安装elasticsearch,elasticsearch-head,kibana,ik分词器安装方式基本有两种,一种是pull的方式,一种是Dockerfile的方式,由于pull的方式pull下来后还需配置许多东西且不便于复用,个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码
文章浏览阅读1.3w次,点赞57次,收藏92次。整理 | 郑丽媛出品 | CSDN(ID:CSDNnews)近年来,随着机器学习的兴起,有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块,内置..._beeware
文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年 飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停
文章浏览阅读986次,点赞2次,收藏2次。1.硬性等待让当前线程暂停执行,应用场景:代码执行速度太快了,但是UI元素没有立马加载出来,造成两者不同步,这时候就可以让代码等待一下,再去执行找元素的动作线程休眠,强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待
文章浏览阅读3k次,点赞4次,收藏14次。Java软件工程师职位分析_java岗位分析
文章浏览阅读2k次。Java:Unreachable code的解决方法_java unreachable code
文章浏览阅读1w次。1、html中设置标签data-*的值 标题 11111 222222、点击获取当前标签的data-url的值$('dd').on('click', function() { var urlVal = $(this).data('ur_如何根据data-*属性获取对应的标签对象