力扣198题动态规划的解题思路和步骤 C++代码实现 力扣(leetcode)

力扣198题是关于打家劫舍的动态规划问题，要求在不触动相邻房屋的情况下，计算出能偷到的最大金额。本文将详细解析解题思路和步骤，并提供C++代码实现。

问题描述

力扣198题要求我们处理一个小偷打家劫舍的场景，他需要在不触动相邻房屋的情况下，计算出能偷到的最大金额。这个问题可以通过动态规划（Dynamic Programming, DP）来解决，其中每个状态代表当前决策下的最大收益。

动态规划基础

动态规划是一种通过将复杂问题分解为更简单的子问题来解决的方法。对于力扣198题，我们定义状态dp[i]为考虑前i个房子时，能偷到的最大金额。状态转移方程为：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，其中nums[i]是第i个房子的金额。

状态转移方程

状态转移方程是动态规划中的核心，它描述了如何从已知状态推导出新状态。对于力扣198题，我们需要根据当前房子是否被偷来决定状态转移。如果偷了当前房子，那么就不能偷前一个房子，因此需要回溯到前两个房子的状态；如果不偷当前房子，那么最大金额就是前一个房子的最大金额。

代码实现

以下是使用C++实现的力扣198题的代码。代码中使用了vector来存储每个状态的最大金额，并根据状态转移方程进行计算。

    #include <vector>
    #include <algorithm>
    using namespace std;
    int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    return dp[n-1];
    }

案例分析

考虑一个案例，nums = [2, 7, 9, 3, 1]。根据动态规划的计算，我们可以得到以下状态转移过程：

- dp[0] = 2- dp[1] = max(2, 7) = 7- dp[2] = max(7, 2 + 9) = 16- dp[3] = max(16, 7 + 3) = 19- dp[4] = max(19, 16 + 1) = 20

最终，dp[n-1] = 20，即为能偷到的最大金额。

本文详细解析了力扣198题的动态规划解题思路和步骤，并提供了C++代码实现。通过定义状态dp[i]和状态转移方程，我们可以计算出在不触动相邻房屋的情况下，能偷到的最大金额。这个问题展示了动态规划在解决优化问题中的应用，通过将复杂问题分解为更简单的子问题，可以有效地找到最优解。