Upperlan
0%

算法系列-动态规划

发表于 更新于 分类于

198. 打家劫舍

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

这题主要是抓住状态转移公式

1.定义dp序列的含义，是如果在0-i索引的房屋偷的时候最高价值是多少

2.初始化，0的时候就是0，1的时候就是看0和1谁大

3.状态转移公式，如果i-1被选了，i就不能选，如果i要被选，则上一个被选的就是i-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int max(int a, int b) {
        return a > b ? a : b;
    }
    int rob(vector<int>& nums) {
        int dp[nums.size()];
        if(nums.size() == 1) return nums[0];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 1;i < nums.size();i++) {
            if(i == 1) {
                dp[i] = max(nums[0], nums[1]);
            }
            else {
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
            }
        }
        return dp[nums.size() - 1];

    }
};

32. 最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：

输入：s = “”
输出：0

dp[i]是当包括s[i]时，连续有效括号的子串长度。

这题主要是对每一个s[i]的处理和判断，牵扯到对s[i - 1]的处理。

当s[i] == ‘(‘时，因为要求必须连续的括号，所以必须为0，要不然递推的时候就会保留不连续的构成符号的最大长度。

当s[i] == ‘)’时，考虑i-1如果正好是’(‘，可以匹配上时，直接与i-2的状态想加就行，最难的是i-1是’)’就要考虑前面的这个是否能构成括号，因此需要考虑一个i-dp[i - 1] - 1这个位置，整好对应第s[i]这个反括号的相应正括号应该存在的地方，这个地方是否是正括号决定了是否能构成有效括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        int maxVal = 0;
        for(int i = 1; i < n; i ++) {
            if(s[i] == ')') {
                if(s[i - 1] == '(') {
                    dp[i] = 2;
                    if(i - 2 > 0) {//注意判断条件
                        dp[i] = dp[i] + dp[i - 2];
                    }
                }
                else {//第一个判别式必须取等号，否则s[0]位置上如果有正括号会漏掉
                    if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                        dp[i] = 2 + dp[i - 1];
                        if(i - dp[i - 1] - 2 > 0) {
                            dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                        }
                    }
                }
            }
            maxVal = max(maxVal, dp[i]);
        }
        return maxVal;

    }
};

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：

输入：nums = [1], target = 1
输出：1

此题是需要利用数学推理，将该问题转变成一个背包问题。

假设被置为负数的元素，其正数和为nag，所有元素正数和为sum，则有sum - nag - nag = target。

所以nag = (sum - target) / 2, 如果nag不为正整数，则无解。

此时就变成了从nums中选一些数，和为nag，即一个背包问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = 0;
        for(auto num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if(diff < 0 || diff % 2 != 0) return 0; 
        int nag = (sum - target) / 2;
        vector<vector<int>> dp(n + 1, vector<int>(nag + 1, 0));//根据dp数组的定义来确定是否+1
        //因为j的索引取值是有含义的，为选取的值的和，所以索引会取到nag值，因此数组大小必须+1
        dp[0][0] = 1;
        for(int i = 1;i <= n; i++) {
            int num = nums[i - 1];
            for(int j = 0; j <= nag; j++) {
                dp[i][j] = dp[i - 1][j];
                if(num <= j) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][nag];

    }
};