动态规划

2021/5/23 18:55:41

本文主要是介绍动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Dynamic Programming

  1. 动态规划一般是求最值、最优问题
  2. 而这种问题每一步局部最优不一定会让最终结果最优(否则就用贪心算法了)
  3. 多种策略计算最终结果,且各种策略之间会出现重复计算

典型动态规划步骤

一、列出变量或数组

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];
    }
}


这篇关于动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程