动态规划

基本要素

转移方程+边界条件

爬楼梯 70

题目分析

1. 转移方程：\(f(x)=f(x - 1)+f(x + 1)\)

2. 边界条件： \(f(0)=1,f(1)=1\) 元方案要求唯一性

由于\(f(x)\)只和\(f(x - 1),f(x - 2)\)有关，故使用滚动数组优化空间复杂度

代码实现

//滚动数组
int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; i ++) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}
//dp数组
class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        int* dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i ++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

使用最小花费爬楼梯

题目分析

cost数组长度len代表了路径中的楼梯数, 则len个阶梯分别对应了数组下标中0到\(n - 1\)的部分, 本题即求到达下标为n的楼梯所需要的最小花费

与上一道题类似, 这道题也是将爬n个台阶的问题, 转化为了爬\((n-1)+1\)个台阶和\((n-2)+2\)个台阶的问题, 由此得到该问题的状态转移方程

\(dp[n] = min(dp[n-1] + cost[n-1], dp[n-2] + cost[n-2])\)

有点贪心的思想, 每一步都取到最小值的话, 最终结果一定最小 考虑边界条件, 由题设我们知道, 起点可以在下标为0或1的楼梯中选取, 所以到达这两个楼梯的前驱花费一定为0

dp[0] = 0
dp[1] = 0

有了状态转移方程与边界条件, 就可以着手开始解题了

代码实现

利用动态数组节省空间的代码如下

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int len = cost.size();
        int prev, curr, next;
        prev = 0; curr = 0;
        for (int i = 0; i <= len; i ++) {
            int func1 = prev + cost[i - 1];
            int func2 = prev + cost[i - 2];
            next = func1 > func2? func1 : func2;
            prev = curr;
            curr = next;
        }
        return curr;
    }
};

删除并获得点数

C++哈希表实现

#include <unordered_map>

unordered_map<int, int> hashtable;
hashtable[key] = value; //insert操作
cout << hashtable[key1] << endl; //按键索值

思路与代码

选取数是任意的，如果每取一个值便要执行删除操作，1是无法进行回溯寻求最优解，2是时间复杂度大，故对vector数组进行排序：

sort(nums.begin(), nums.end());

又因为一旦一个值被选取，则与他相同的值均可以被选取，故使用hash表对每个值与其出现的次数进行存储，能优化时间与空间复杂度

接下来考虑状态转移方程，此时问题已经转化为了：在一个有序单调数组中顺序取数，在取了一个数num后，则不能选取num + 1（因为取数操作从无序数组转为有序数组，故而考虑num - 1与考虑num + 1性质相同），而为了获得最大点数，我们必须权衡选取num与选取num + 1两个操作，究竟哪个利润最大

由此得到对于第i个数据对象的状态转移方程

if dp[i] - dp[i - 1] == 1
dp[i] = max(dp[i - 1], dp[i] * N + dp[i - 2])
else 
dp[i] = dp[i] * N + dp[i - 2]

由于要考虑选和不选的问题，我们使用一个变量last存储当前的dp[i],也就是下一轮循环的前驱了

对于边界条件，我们考虑到value初始值为0的情况，为了避免对首元素的讨论，我们让dp数组的首元素取0即可

代码如下：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int, int> m; //记录每一个值出现了多少次
        sort(nums.begin(), nums.end());
        vector<int> dp = {0, nums[0]}; //起始两个数
        m[nums[0]] = 1;
        for (int i = 1; i < nums.size(); i ++) {
            m[nums[i]] ++;
            if (nums[i] != dp.back())
                dp.push_back(nums[i]);
        }
        int last = dp[1];
        dp[1] = dp[1] * m[dp[1]];
        for (int i = 2; i < dp.size(); i ++) {
            if (dp[i] - last == 1) {
                last = d[i];
                dp[i] = max(dp[i - 1], dp[i - 2] + dp[i] * m[dp[i]]);
            } else {
                last = dp[i];
                dp[i] = dp[i - 1] + dp[i] * m[dp[i]];
            }
        }
        return dp[dp.size() - 1];
    }
};

最长有效括号 32

问题分析

求最长括号字串长度, 考虑动态规划

在动态规划问题中, 注重的是由小到大, 由浅入深的问题累积过程. 在本题中, 我们设下标i代表当前括号字符串s的第i个元素, dp[i]表示以当前元素结尾并包含当前元素在内的最长有效括号字串, 下面的讨论以上述条件为依托展开

• 状态转移方程 由于dp[i]表示的是最长有效括号字串, 故要使其值不等于零, 则须满足s[i] \(=\) ')' , 对s[i - 1]进行讨论:

  1. s[i - 1] == '(' 
      此时s[i - 1]与s[i]构成一对有效括号, dp[i]至少为2
      赋值操作: dp[i] = 2
      若在此基础上, s[i - 2]存在且dp[i - 2] != 0
      说明s[i - 2]是一条有效括号字串的结尾
      dp[i] = dp[i] + dp[i - 2]
  2. s[i - 1] == ')'
      若dp[i - 1] == 0, 说明s[i - 1]为一条有效括号字串的结尾
      为了知道s[i]是否为一条有效括号字串的结尾
      我们需要考虑下标i - dp[i - 1] - 1的存在性
      若其不存在 则s[i]不是有效结尾
      若其存在,且s[i - dp[i - 1] - 1] == '('
      说明s[i]是有效结尾
      dp[i]至少为dp[i - 1] + 2
      赋值操作: dp[i] = dp[i - 1] + 2;
      若再此基础上, s[i - dp[i - 1] - 2]存在
      且dp[i - dp[i - 1] - 2] != 0
      说明s[i - dp[i - 1] - 2]是一条有效括号的结尾
      dp[i] = dp[i] + dp[i - dp[i - 1] + 2]
  

• 边界条件 我们知道, dp[0] == 0, 因为单个括号不可能有效

在代码实现中, 只需要考虑下标的非负性即可

代码实现

class Solution {
public:
    int longestValidParentheses(string s) {
        int size = s.length();
        vector(int) dp(size, 0);
        int maxval = 0;
        for (int i = 1; i < size; i ++) {
            if (s[i] == '(') {
                dp[i] = 0;
            } else if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = 2;
                    if (i - 2 >= 0) {
                        dp[i] += dp[i - 2];
                    }
                } else if (dp[i - 1] > 0 ) {
                    if (i - dp[i - 1] - 1 >= 0 && dp[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (i - dp[i - 1] - 2 >= 0) {
                            dp[i] += dp[i - dp[i - 1] + 2];
                        }
                    }
                }
            }
            maxval = max(dp[i], maxval);
        }
        return maxval;
    }
}

最长回文字串 5