01一维动态规划
# 01 一维动态规划
# 70 爬楼梯 (opens new window)
给定 n 节台阶,每次可以走一步或走两步,求一共有多少种方式可以走完这些台阶。
输入是一个数字,表示台阶数量;输出是爬台阶的总方式。
输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
解析:
这是十分经典的斐波那契数列题。
设置状态:定义一个数组 dp,dp[i]
表示走到第 i 阶的方法数
状态转移方程:因为我们每次可以走一步或者两步,所以第 i 阶可以从第 i-1 或 i-2 阶到达。换句话说,走到第 i 阶的方法数即为走到第 i-1 阶的方法数加上走到第 i-2 阶的方法数。这样我们就得到了状态转移方程dp[i] = dp[i-1] + dp[i-2]
。
初始情况:当阶数小于等于1时,方法数为1
class Solution {
public:
int climbStairs(int n) {
if(n<2) return n;
vector<int> dp(n+1);
dp[0] = dp[1] = 1;
for(int i=2;i<=n;++i){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
# 198 打家劫舍 (opens new window)
假如你是一个劫匪,并且决定抢劫一条街上的房子,每个房子内的钱财数量各不相同。如果你抢了两栋相邻的房子,则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。
输入是一个一维数组,表示每个房子的钱财数量;输出是劫匪可以最多抢劫的钱财数量。
输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
解析:
设置状态:定义一个数组 dp,dp[i]
表示抢劫到第 i 个房子时,可以抢劫的最大数量。
状态转移方程:我们考虑 dp[i]
,此时可以抢劫的最大数量有两种可能,一种是我们选择不抢劫这个房子,此时累计的金额即为dp[i-1]
;另一种是我们选择抢劫这个房子,那么此前累计的最大金额只能是 dp[i-2]
,因为我们不能够抢劫第 i-1 个房子,否则会触发警报机关。因此本题的状态转移方程为 dp[i] = max(dp[i-1],nums[i-1] + dp[i-2])
。
初始情况:第一个房子的抢劫最大数量 dp[1] = nums[0]
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty()){
return 0;
}
int len = nums.size();
vector<int> dp(len+1,0);
dp[1] = nums[0];
for(int i=2;i<=len;++i){
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
}
return dp[len];
}
};
# 213 打家劫舍 II (opens new window)
假如你是一个劫匪,并且决定抢劫一条街上的房子,这条街所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。如果你抢了两栋相邻的房子,则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。
输入是一个一维数组,表示每个房子的钱财数量;输出是劫匪可以最多抢劫的钱财数量。
输入:nums = [2,3,2] 输出:3 解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
解析:
本题与198题的主要区别是输入的一维数组是一个环形数组,所以要分别考虑抢第一个房子和不抢第一个房子的情况。抢第一个房子,那么就不能抢最后一个房子,则可抢的范围为nums[0]~nums[len-2]
;不抢第一个房子,那么就可以抢最后一个房子,则可抢的范围为nums[1]~nums[len-1]
。
基于上述两种情况使用与198题相同的动态规划方法解决本问题
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if(len < 1) return 0;
vector<int> nums1,nums2;
for(int i=0;i<len;++i){
if(i==0){
nums1.push_back(nums[i]);
}else if(i==len-1){
nums2.push_back(nums[i]);
}else{
nums1.push_back(nums[i]);
nums2.push_back(nums[i]);
}
}
return max(robRange(nums1),robRange(nums2));
}
int robRange(vector<int>& nums){
int len = nums.size();
if(len < 1) return 0;
vector<int> dp(len+1,0);
dp[1] = nums[0];
for(int i=2;i<=len;++i){
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
}
return dp[len];
}
};
上述解法较为直观,先分情况在计算最大抢劫价值;也可以通过划分区间的方式划分情况如下
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if(len == 1) return nums[0];
return max(robRange(nums,0,len-1),robRange(nums,1,len));
}
int robRange(vector<int>& nums, int start, int end){
int len = end - start;
if(len < 1) return 0;
vector<int> dp(len+1,0);
dp[1] = nums[start];
for(int i=2;i<=len;++i){
dp[i] = max(dp[i-1],dp[i-2]+nums[i+start-1]);
}
return dp[len];
}
};
# 413 等差数列划分 (opens new window)
给定一个数组,求这个数组中连续且等差的子数组一共有多少个。
输入是一个一维数组,输出是满足等差条件的连续字数组个数。
输入:nums = [1,2,3,4] 输出:3 解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
解析:
这道题略微特殊,因为要求是等差数列,可以很自然的想到子数组必定满足 num[i] - num[i-1] = num[i-1] - num[i-2]
。然而由于我们对于 dp 数组的定义通常为以 i 结尾的,满足某些条件的子数组数量,而等差子数组可以在任意一个位置终结,因此此题在最后需要对 dp 数组求和。
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int len = nums.size();
int res = 0;
if(len < 3){
return res;
}
vector<int> dp(len,0);
for(int i = 2;i<len;++i){
if(nums[i]-nums[i-1] == nums[i-1] - nums[i-2]){
dp[i] = dp[i-1] + 1;
res += dp[i];
}
}
return res;
}
};
# 53 最大子序和 (opens new window)
给定一个数组,找出一个具有最大和的连续子数组,并返回其最大和。
输入一个数组,输出一个整数,为连续子数组的最大和
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
解析:
设置状态:使用一维数组dp[i]
表示以第 i 个元素结尾的子序列的最大和
状态转移方程:我们考虑 dp[i]
,此时构成最大和的子序列有两种可能,一种是我们选择不将第 i 个元素加入子序列,因为要构成连续的子序列,所以自己单独构成新的子序列此时最大和即为自身nums[i-1]
;另一种是我们选择将第 i 个元素加入子序列,那么构成子序列的最大和为dp[i-1]+nums[i-1]
。所以本题的状态转移方程为 dp[i] = max(nums[i-1],nums[i-1] + dp[i-1])
。
初始情况:只有一个元素,dp[1]=nums[0]
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
if(len < 1) return 0;
vector<int> dp(len+1,0);
dp[1] = nums[0];
int ans = nums[0];
for(int i=2;i<=len;++i){
dp[i] = max(nums[i-1],dp[i-1]+nums[i-1]);
ans = max(ans,dp[i]);
}
return ans;
}
};