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