动态规划

爬楼梯问题

1. 题目

爬楼梯每次可以爬1阶或两阶，问到n阶有多少种方法

2. 思路

状态：dp[i]表示到第i阶的走法
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
边界状态值：dp[1] = 1, dp[2] = 2

3. 代码

int climbStairs(int n)
{
    std::vector<int> dp(n+3, 0);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

打家劫舍

1. 题目

一组相邻的n个房屋，每个房屋有不等数量的财宝，盗贼想要盗取财物，但是从相邻的房屋盗取会出发警报，问在不触发警报的情况下，最多可以盗取多少财宝？

2. 思路

• 状态：dp[i]表示前i个房间能获得的最大财宝
• 状态转移方程：
  如果选择第i个房间，dp[i] = dp[i-2] + dp[i]；不选择第i个房间，dp[i] = dp[i-1]；
  所以dp[i]的最优解为dp[i] = max(dp[i-2] + dp[i], dp[i-1])
• 边界状态值：
  dp[0] = num[0],
  dp[1] = max(num[0], num[1])

3. 代码

int rot(std::vector<int> &nums)
{
    if (nums.size() == 0) {
        return 0;
    }
    if (nums.size() == 1) {
        return nums[0];
    }
    std::vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    dp[1] = std::max(nums[0], nums[1]);
    for (int i = 2; i < nums.size(); i++) {
        dp[i] = std::max(dp[i-1], dp[i-2]+nums[i]);
    }
    return dp[nums.size() - 1 ];
}

最大子段和

1. 题目

给定一个数组，求这个数组的连续子数组中，最大的那一段的和

2. 思路

• 状态：dp[i] 表示以第i个数字结尾的最大子段和
• 状态转移方程
  若dp[i-1] > 0, dp[i] = dp[i-1] + num[i]
  若dp[i-1] < 0, dp[i] = num[i]
  所以：dp[i] = max(dp[i-1] + num[i], num[i])
• 边界状态值：dp[0] = num[0]

3. 代码

int maxSubArray(std::vector<int> &num)
{
    std::vector<int> dp(num.size(), 0);
    dp[0] = num[0];
    int max_res = dp[0];

    for (int i = 1; i < num.size(); i++) {
        dp[i] = std::max(dp[i - 1] + num[i], num[i]);  // 状态转移方程
        if (max_res < dp[i]) {
            max_res = dp[i];
        }
    }
    return max_res;
}