【动态规划】闫氏dp分析

摘要:
Yan的dp分析和Acwingyxc的解释。本文是几个经典示例的注释目录53.最大子顺序和120。三角形最小路径和91。解码方法62.不同路径63.不同路径II198。入室抢劫72.编辑距离53.最大次顺序和给定整数数组num,找到具有最大和的连续子数组并返回其最大和。初始化:设置分区:返回结果:publicintmaxSubArray{int[]f=newint[nums.length];f[0]=nums[0];interts=f[0];for{f[i]=Math.max+nums[i];res=Math.max;}返回符;}时间复杂度:状态数为O,传输时间为O,总时间为O。状态表示的属性为:数量。设置分区:最后一个步骤向下:最后一步向右:结果:返回结果:[f[i][j]=egin{cases}1,&mbox{i=0orj=0}dp[i-1][j]+dp[i]

来源于Acwing yxc的闫氏dp分析讲解,本文为几道经典例题的笔记

目录

53. 最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

状态表示(f[i])表示以第i个数字为结尾的是最大连续子序列的总和 。

状态表示的属性:max最大值。

初始化(f[0] = nums[0])

集合的划分【转移方程】: (f[i] = max(f[i - 1], 0)+ nums[i])

返回结果(res = max(f[0],f[1],f[2]...f[n]))

    public int maxSubArray(int[] nums) {
        int[] f = new int[nums.length];
        f[0] = nums[0];
        int res = f[0];
        for(int i = 1; i < nums.length; i++){
            f[i] = Math.max(f[i - 1],0) + nums[i];
            res = Math.max(res, f[i]);
        }
        return res;
    }

时间复杂度:状态数为O(N),转移时间为O(1),总时间为O(N)。

空间复杂度:需要额外O(N)的空间存储状态。

优化:通过变量代替数组存储空间复杂度,优化到常数。

    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE, prev = 0;
        for(int i = 0; i < nums.length; i++){
            int now = Math.max(prev,0) + nums[i];
            res = Math.max(now, res);
            prev = now;
        }
        return res;
    }

120. 三角形最小路径和

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

相邻的结点 在这里指的是 下标上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如,给定三角形:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

状态表示:$f[i][j] $表示所有从起点走到第i行,第j个数的路径

状态表示的属性:所有路径上的数的和的最小值。

初始化(f[0][0] = t.get(0).get(0))

集合的划分【转移方程】:

  • 最后一步从左上方下来的:(left = f[i-1][j-1]+ nums[i][j])
  • 最后一步从右上方下来的:(right = f[i-1][j] + nums[i][j])
  • 结果:(f[i][j] = min(left, right))

返回结果(res = min(f[n-1][1-> n-1]))

    public int minimumTotal(List<List<Integer>> t) {
        int n = t.size();
        int[][] f = new int[2][n]; //f[i][j]代表从起点走到第i行第j列的最小值
        f[0][0] = t.get(0).get(0);
        for(int i = 1; i < n; i ++){
            for(int j = 0; j <= i ; j ++){
                f[i&1][j] = Integer.MAX_VALUE;
                if(j > 0) f[i&1][j] = Math.min(f[i&1][j],f[i-1&1][j-1]+t.get(i).get(j));//代表上下层坐标相等的情况
                if( j < i) f[i&1][j] = Math.min(f[i&1][j],f[i-1&1][j]+t.get(i).get(j));//代表是上层下层坐标相等的情况
                
            }
        }
        int res = Integer.MAX_VALUE;
        for(int i = 0; i< n; i++){
            res = Math.min(res,f[n-1&1][i]);
        }//返回结果为最后一层的最小值  min(f[n-1][0->n-1])
        return res;
    }

91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码:

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串,请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

状态表示(f[i])表示所有由前i个数字解码得到的字符串 。

状态表示的属性:数量。

初始化(f[0] = 1)

集合的划分【转移方程】:

  • 最后一个字母由(s[i])解码【最后一位是一位数】:(cnt1 = f[i - 1])

  • 最后一个字母由(s[i - 1],s[i])解码【最后一位是两位数】: (cnt2 = f[i - 2])

  • (f[i] = cnt1 + cnt2)

返回结果(res = f[n])

    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1]; //减少边界的判断
        char[] chs = s.toCharArray();
        f[0] = 1;
        for(int i = 1; i<= n ; i++){
            if( chs[i - 1]!= '0') f[i] += f[i - 1];
            if(i >= 2){
                int t = (chs[i - 2] -'0') * 10 + chs[i - 1] -'0';
                if( t>= 10 && t<=26) f[i] += f[i - 2];
            }
        }
        return f[n];
    }

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

【动态规划】闫氏dp分析第1张

例如,上图是一个7 x 3 的网格。有多少可能的路径?

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10 ^ 9

状态表示:$f[i][j] (表示所有从起点走到)[i,j]$的路径

状态表示的属性:路径的数量。

初始化:第一行第一列都在边界上,路径为1,因此f[0][j]f[i][0]都为1。

集合的划分【转移方程】:

  • 最后一步向下走:(down = f[i-1][j])
  • 最后一步向右走:(right = f[i][j -1])
  • 结果:(f[i][j] = down + right)

返回结果(res = f[i-1][j-1])

  • [f[i][j] = egin{cases} 1,& mbox{i = 0 or j = 0} \ dp[i - 1][j] + dp[i][j - 1], & mbox{others} end{cases} ]

    public int uniquePaths(int m, int n) {
        //f[m,n]表示走到m,n的路径 res = f[m-1][n-1]
        int[][] f = new int[m][n];

        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0) f[i][j] = 1;
                else f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

【动态规划】闫氏dp分析第2张

网格中的障碍物和空位置分别用 10 来表示。

说明:m 和n的值均不超过 100。

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

状态表示:$f[i][j] (表示所有从起点走到)[i,j]$的路径

状态表示的属性:路径的数量。

初始化:第一行,第一列的路径数。

集合的划分【转移方程】:

  • 最后一步向下走:(down = f[i-1][j])
  • 最后一步向右走:(right = f[i][j -1])
  • 结果:(f[i][j] = down + right)

返回结果(res = f[i-1][j-1])

class Solution {
    public int uniquePathsWithObstacles(int[][] g) {
        if (g == null || g.length == 0) {
            return 0;
        } 
        // 定义 dp 数组并初始化第 1 行和第 1 列。
        int m = g.length, n = g[0].length;
        int[][] f = new int[m][n];
        
        for(int i = 0; i < m && g[i][0] != 1; i++){ //为第一行的路径赋值,直到遇到障碍物
            f[i][0] = 1;
        }

        for(int i = 0; i < n && g[0][i] != 1; i++){//为第一列的路径赋值,直到遇到障碍物
            f[0][i] = 1;
        }
        for(int i = 1; i < m; i ++){
            for(int j = 1; j < n; j++){
                
                if(g[i][j] == 1) continue; //如果遇到障碍物,跳过,默认为0
                else{
                    f[i][j] = f[i - 1][j] + f[i][j - 1];//等于上面来的+左面来的
                }
            }
        }
        return f[m - 1][n - 1];
    }
}

另一种做法:

    public int uniquePathsWithObstacles(int[][] g) {
        if (g == null || g.length == 0) {
            return 0;
        } 
        // 定义 dp 数组并初始化第 1 行和第 1 列。
        int m = g.length, n = g[0].length;
        int[][] f = new int[m][n];
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j++){
                if(g[i][j] == 1) continue; //遇到障碍物 跳过
                if( i == 0 && j == 0 ) f[i][j] = 1; //左上角顶点处,初始化为1
                if( i > 0 ) f[i][j] += f[i - 1][j];
                if( j > 0 ) f[i][j] += f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }

198. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];//n+1 长度,不再需要考虑边界问题 [x,1,2,3,4 ....n] 1-n
        int[] g = new int[n+1];
        for(int i = 1; i <= n; i++){
            f[i] = Math.max(f[i-1],g[i-1]);//f[i]代表没选num[i]的Max
            g[i] = f[i-1]+nums[i-1]; // g[i]代表选nums[i]的选法max
        }   
        return Math.max(f[n],g[n]);
    }

72. 编辑距离

给你两个单词 word1word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

状态表示:$f[i][j] (所有将第一个字符串前)i(个字母变成第二个字符串前)j$个字母的方案

状态表示的属性:最小值。

初始化:其中一个字符串为空,结果为另一个字符串的长度。

集合的划分【转移方程】:

  • insert:(f[i] = f[i,j-1]+1),还没插的时候,前(i)个字母已经和word2的前(j-1)个字母相同,插入(word[j])才可能相同,因此操作数是(f[i,j-1]+1)
  • delete:(f[i-1,j]+1) 保证删除之后和w1和w2相同,表示(i)之前的数和(j)同。
  • replace:(f[i-1,j-1]+1) 表示将w1前面的所有数转化为w2,再加上replace操作。
  • 不需要替换:不需要替换 (f[i-1][j-1]),第(i)个字母和第(j)个字母相等。
  • 结果(f[i][j] = min(f_1,f_2,f_3,f_4))

返回结果:$res = f[m][n] $

    public int minDistance(String word1, String word2) {
        char[] ch1 = word1.toCharArray();
        char[] ch2 = word2.toCharArray();
        int n1 = word1.length(),n2 = word2.length();
        int[][] f = new int[n1+1][n2+1];
        for(int i = 0; i <= n1; i++) f[i][0] = i; //填边
        for(int i = 0; i <= n2; i++) f[0][i] = i;
        for(int i = 1; i <= n1 ; i++){
            for(int j = 1; j<= n2; j++){
                f[i][j] = Math.min(f[i-1][j],f[i][j-1])+1;// insert和delete
                int rep = 0;//交换的操作
                if(ch1[i-1] != ch2[j-1]){
                    rep = 1;
                }
                f[i][j] = Math.min(f[i][j],f[i-1][j-1]+rep); // replace or not
            }
        }
        return f[n1][n2]; 
    }

免责声明:文章转载自《【动态规划】闫氏dp分析》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇pip安装使用详解Centos7中一次性安装开发者工具下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

数字组合(动态规划)

数字组合 时间限制: 1 Sec  内存限制: 256 MB提交: 30  解决: 24[提交][状态][讨论版] 题目描述 在 N个数中找出其和为M的若干个数。先读入正整数N(1<N<100)和M(1<M<10000), 再读入N个正数(可以有相同的数字,每个数字均在1000以内), 在这N个数中找出若干个数, 使它们的和是M,...

斐波那契数列(动态规划)

#include "stdafx.h" #include <iostream> using namespace std; #define MAXSIZE 100 int bofei_bottom(int n) { int f[MAXSIZE]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n;...

嵌套矩形(动态规划)

思路: 先把这些矩形统一 一下,让最长边向下,然后按大小放好。 这样,我们就可以来构建DAG图形, 令,被包含的矩形a与包含的矩形b看成a一一>b的路线,这样就形成了这样的图形: ,我们一定知道最小矩形一定是不能包含其他矩形的(因为没有矩形比最小矩形还小),同时,知道最大矩形一定不能被包含。(因为没有矩形比最大矩形大) 为什么,我们要考虑最大和最小矩...

Max Sum Plus Plus (动态规划) HDU1024

题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1024 (http://www.fjutacm.com/Problem.jsp?pid=1375) 题意:长度为n的序列里,m段不相关区间的最大和 思路:我们先要确定一个东西,就是状态,这里我用dp[i][j]表示前j个数在取a[j]情况下分i段的最大和; 那么...

动态规划解决01背包问题

一、问题描述:有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 二、总体思路:根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现; 三、动态规划的原理及过程: eg:numb...

数据结构 练习 19-活动选择问题的实现(动态规划 和 贪心)

问题叙述:如下图表示活动的开始和结束时间,s[i],开始时间;f[j]结束时间。现在要进行一些列如下活动,注意每个时间段只能进行一场活动,也就是活动不能同时进行,要求举行的活动次数最多。求调度方法。 老规矩,动态规划,要找出两个问题: 1,子问题的最优解; 2,子问题是什么。 abviously,本问题的最优解为:活动数的次数最多,子问题是:看递推公式...