动态规划
2021/5/23 18:55:41
本文主要是介绍动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Dynamic Programming
- 动态规划一般是求最值、最优问题
- 而这种问题每一步局部最优不一定会让最终结果最优(否则就用贪心算法了)
- 多种策略计算最终结果,且各种策略之间会出现重复计算
典型动态规划步骤
一、列出变量或数组
1、如果是一维数组问题 ==> 声明一个变量并初始化:int dp = nums[0];
;
2、如果是二维数组问题 ==> 声明一个数组并初始化第一个值:int[] pd = new int[n+1];
二、写出状态转移方程
f[x] = min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
(x>=7)注意要列出变量范围
三、实现代码
实例
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大为6
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
import java.util.*; class Solution { public int maxSubArray(int[] nums) { int dp = nums[0]; int max = dp; for(int i=1;i<nums.length;i++){ dp = Math.max(dp+nums[i],nums[i]); if(max < dp) max = dp; } return max; } }
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
输入: [ [1,3,1], [1,5,1], [4,2,1] ]
输出: 12
解释: 路径 1→3→5→2→1可以拿到最多价值的礼物
提示:
0 < grid.length <= 200
0 < grid[0].length <= 200
思路: 二维数组从左到右,从上到下遍历:
import java.util.*; class Solution { public int maxValue(int[][] grid) { int[] pd = new int[grid[0].length+1]; for(int m=0;m<grid.length;m++){ for(int n=0;n<grid[0].length;n++){ pd[n+1] = Math.max(pd[n],pd[n+1]) + grid[m][n]; } } return pd[grid[0].length]; } }
这篇关于动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南