简单DP入门: 线性DP

题均源自0x3f的题单,如有雷同,不是巧合

记忆化搜索是新手入门很好的帮助,而自顶向上的递推可以让我们更容易的使用数据结构和其他技巧优化时间和空间复杂度

因此刚刚接触动态规划的时候如果写了记忆化后尽量都尝试改为递推DP再写一遍(数位DP等特殊情况除外)

本节会实现三个较为基础的动态规划问题与其变形:

爬楼梯
打家劫舍
最大子数组和

Section1.0 爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路

这可以看做一个递归问题 $f_{n} = f_{n - 1} + f_{n - 2}$

(当然或许你可以看出来这就是一个斐波那契数列)

你会发现这其实有大量的重复计算,比如我们要算 $f_{5}$ 会计算 $f_{4}$ 和 $f_{3}$ ,然而算 $f_{4}$ 的时候我们又要算了一遍 $f_{3}$

所以这个时候我们引入哈希表用于处理重复计算过的问题(重叠子问题),如果当前 $f_{n}$ 已经算过,就直接返回保存的答案

这样每个问题搜索次数都是 $O (1)$ 的,总共有 $n$ 个问题,所以是 $O (n)$ 的

这就是动态规划的基本思想

代码

上述过程可以这样实现:

cpp

map<int,int> cache;
int climbStairs(int n) {
    if(n<=2)return max(0  ,n);
    if(!cache.count(n))
    cache[n]=climbStairs(n-1)+climbStairs(n-2);
    return cache[n];
}

转为递推

cpp

int climbStairs(int n) {
  int dp[n+2];
  dp[0]=1;
  dp[1]=2;
  for(int i=2;i<n;i++){
      dp[i]=dp[i-1]+dp[i-2];
  }
  return dp[n-1];
}

注意到我们转移的时候只用到了 $d p_{i - 1}$ 和 $d p_{i - 2}$ ,所以可以用滚动数组把空间可以压到 $O (1)$

cpp

int climbStairs(int n) {
    int a=1,b=2;
    if(n==1)return a;
    for(int i=2;i<n;i++){
        int tmp=b;
        b+=a;
        a=tmp;
    }
    return b;
}

Section1.1 使用最小花费爬楼梯

题目

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

思路

我们一般习惯dp入口唯一,所以倒序dp

代码

cpp

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        int dp[n+5];
        memset(dp,0,sizeof(dp));
        for(int i=n-1;i>=0;i--){
            dp[i]=cost[i]+min(dp[i+1],dp[i+2]);
        }
        return min(dp[0],dp[1]);
    }
};

这题依然可以滚动数组优化,可以自行尝试实现

Section1.2 组合总和 Ⅳ

题目

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素互不相同
1 <= target <= 1000

思路

一个比较有趣的角度看这道题:

将target视为最后的台阶,每次可以向上走 $n u m s_{i}$ 个台阶,然后求方案,从这个角度来说就是第一题的升级版

代码

cpp

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        unsigned dp[target+5];
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=1;i<=target;i++){
            dp[i]=0;
            for(int j=0;j<nums.size();j++){
                if(i-nums[j]>=0){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
};

要注意的是这题数据可能会溢出long long,但题目保证最后的答案在32 位整数范围,所以用unsigned避免溢出报错即可

Section1.3 统计构造好字符串的方案数

题目

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

将 '0' 在字符串末尾添加 zero 次。
将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个长度在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为好字符串。

请你返回满足以上要求的不同好字符串数目。由于答案可能很大，请将结果对 1e9 + 7 取余后返回。

思路

依然可以看做爬楼梯

代码

cpp

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        int dp[high+5];
        dp[0]=1;
        int ans=0;
        int MOD=1e9+7;
        for(int i=1;i<=high;i++){
            dp[i]=0;
            if(i>=zero)dp[i]=(dp[i]+dp[i-zero])%MOD;
            if(i>=one)dp[i]=(dp[i]+dp[i-one])%MOD;
            if(i>=low&&i<=high)ans=(ans+dp[i])%MOD;
        }
        return ans;
    }
};

Section1.4 统计打字方案数

题目较长,见这里

综合一点的一道题: 分组+爬楼梯+乘法原理

写了这么多爬楼梯变形,是否感受到相关思想的精髓了?

要注意尽管有取模,加法和乘法的过程还是有可能溢出int的

Section2.0 打家劫舍

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

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

设dp数组为 $f$ ,第 $i$ 间房屋金额为 $v_{i}$ ,则有转移方程:

f_{i} = m a x (f_{i - 1}, f_{i - 2} + v_{i})

Section2.1 删除并获得点数

题目

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

思路

不难发现,nums[i] - 1 和 nums[i] + 1 其实就是nums[i]值域上的相邻,从单顺序贪心来考虑的话对于i我们只需要考虑 nums[i-1] 的影响即可

实际上就是值域上的打家劫舍

所以统计一下重复的点数用哈希表记一下,然后去重再dp

转移方程如下:

f_{i} = {\begin{cases} max (f_{i - 1}, f_{i - 2} + a_{i} \cdot c n t_{i}) & if a_{i} = a_{i - 1} + 1 \\ f_{i - 1} + a_{i} \cdot c n t_{i} & otherwise \end{cases}

Section2.2 统计放置房子的方式数

题目

一条街道上共有 n * 2 个地块，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 1e9 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

思路

想清楚转移的定义是什么:

f_{i} = f_{i - 1} + f_{i - 2}

Section2.3 打家劫舍 II

题目

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

思路

比较有一意思的拆环,这里我们可考虑选不选第一个分类讨论来处理环

Section3.0 最大子数组和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

思路

定义 $f_{i}$ 表示以 $i$ 结尾的子数组的最大值,则有转移方程:

f_{i} = m a x (f_{i - 1}, 0) + a_{i}

则MCS即为 $m a x {f_{i} | i \in N}$

Section3.1 任意子数组和的绝对值的最大值

题目

给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的和的绝对值为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。

请你找出 nums 中和的绝对值最大的任意子数组（可能为空），并返回该最大值。

思路

维护一个最大一个最小即可

Section3.2 K 次串联后最大子数组之和

题目

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于结果可能会很大，需要返回的 1e9 + 7 的模。

arr.length<=1e5
k<=1e5

思路

这题有一定的思维难度

首先不难想到暴力做法就是直接在重复k次的数组上跑MCS,但是显然会超时

所以自然我们会去想重复的规律是什么

不难注意到如果数组和 $s >= 0$ 的时候,根据转移方程必然就是基本的dp值直接加上重复n次的数组和

那么最基础的dp值是什么呢? 显然是当 $k = 2$ 的时候存在

所以我们求 $k = 2$ 的MCS,然后如果 $s >= 0$ ,就加上 $s * (k - 2)$

这个时候你会疑问: MCS求得的值不一定是能与后面接上(连续)的啊

但是注意如果 $s >= 0$ 的时候,MCS必然为 $k = 2$ 数组的头/尾,一定可以与后续重复的部分接上

所以正确性无误

代码

cpp

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        long long n=arr.size()*min(k,2),ans=0,s=0,MOD=1e9+7;
        long long dp[n+1];
        dp[0]=0;
        for(int i=0;i<n;i++){
            dp[i+1]=(max(dp[i],0LL)+arr[i%arr.size()]);
            ans=max(ans,dp[i+1]);
        }
        ans%=MOD;
        for(int i=0;i<arr.size();i++) s=(s+arr[i])%MOD;
        if(s>0)ans+=s*(k-min(k,2))%MOD;
        return ans%MOD;
    }
};

同时要注意的一个细节是这里 $d p$ 的时候不能取模,会影响最大值的选择

Section3.3 环形子数组的最大和

思路

成环的时候大难显然是最大MCS或者总和-最小MCS

Section3.4 拼接数组的最大分数

题目

思路

从贡献的角度思考,显然是贡献为数组的差值

对于两数组的差值数组求最小MCS和最大MCS即可,一个丢上面,一个丢下面,然后求max即可

Section1.0 爬楼梯 ​

题目 ​

思路 ​

Section1.1 使用最小花费爬楼梯 ​

题目 ​

思路 ​

Section1.2 组合总和 Ⅳ ​

题目 ​

思路 ​

Section1.3 统计构造好字符串的方案数 ​

题目 ​

思路 ​

Section1.4 统计打字方案数 ​

Section2.0 打家劫舍 ​

Section2.1 删除并获得点数 ​

题目 ​

思路 ​

Section2.2 统计放置房子的方式数 ​

题目 ​

思路 ​

Section2.3 打家劫舍 II ​

题目 ​

思路 ​

Section3.0 最大子数组和 ​

题目 ​

思路 ​

Section3.1 任意子数组和的绝对值的最大值 ​

题目 ​

思路 ​

Section3.2 K 次串联后最大子数组之和 ​

题目 ​

思路 ​

Section3.3 环形子数组的最大和 ​

思路 ​

Section3.4 拼接数组的最大分数 ​

思路 ​

Section1.0 爬楼梯

题目

思路

Section1.1 使用最小花费爬楼梯

题目

思路

Section1.2 组合总和 Ⅳ

题目

思路

Section1.3 统计构造好字符串的方案数

题目

思路

Section1.4 统计打字方案数

Section2.0 打家劫舍

Section2.1 删除并获得点数

题目

思路

Section2.2 统计放置房子的方式数

题目

思路

Section2.3 打家劫舍 II

题目

思路

Section3.0 最大子数组和

题目

思路

Section3.1 任意子数组和的绝对值的最大值

题目

思路

Section3.2 K 次串联后最大子数组之和

题目

思路

Section3.3 环形子数组的最大和

思路

Section3.4 拼接数组的最大分数

思路