一、动态规划的形式就是求最值

其中核心问题是穷举，穷举出所有办法，找出最大或者最小的情况。但是穷举是有技巧的，需要借助“备忘录”或者来“Table”避免重叠子问题的发生。其中找出状态转移方程才能更加有效的解决问题，而这一步往往是最难的。之后就是通过找出最优子结构来得出整体的最优解。

二、正式开始

1. 斐波那契数列

  1. //方法1 暴力递归(这个方法完全过不了的，直接显示超时)
  2. int fib1(int n) {
  3.     if (n == 1 || n == 2)
  4.         return 1;
  5.     return fib(n - 1) + fib(n - 2);
  6. }
  9. //方法2 带备忘录的递归（时间复杂度为n），通过剪枝来降低复杂度
  10. //但是方法二还是在递归，这样无法进行取余
  11. int helper(vector<int>& memo, int n) {
  12.     if (n == 1 || n == 2)
  13.         return 1;
  14.     //查询备忘录，有则直接取备忘录中数据
  15.     if (memo[n] != 0)
  16.         return memo[n];
  18.     memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
  19.     return memo[n];
  20. }
  23. int fib2(int n){
  24.     vector<int> memo(n+1,0);
  25.     return helper(memo,n);
  26. }
  29. //方法3 DP数组迭代（时间复杂度为n，空间复杂度为n）
  30. int fib3(int n) {
  31.     vector<int> DP(n + 1, n);
  32.     DP[1] = DP[2] = 1;
  33.     for (int i = 3; i < n + 1; ++i) {
  34.         DP[i] = DP[i - 1] + DP[i - 2];
  35.     }
  36.     return DP[n];
  37. }
  40. 方法4 压缩的DP迭代(在3基础上，将空间复杂度降为1)
  41. int fib4(int n) {
  42.     if (n == 1 || n == 2) {
  43.         return 1;
  44.     } else {
  45.         int prev = 1, curr = 1;
  46.         for (int i = 3; i < n + 1; ++i) {
  47.             int sum = prev + curr;
  48.             prev = curr;
  49.             curr = sum;
  50.         }
  51.         return curr;

PS：但凡遇到需要递归的问题，最好都画出递归树，这对分析算法的复杂度，寻找算法低效的原因都有
巨大帮助。
！！！！没认真读题，题目要求取模！！
截屏2020-12-01 19.03.37.png

2.爬楼梯

一个人在宿舍，安静，开工！第二题：爬楼梯。很经典一题，不难发现，第n级的爬法就是第n-1级+第n-2级的方法之和。用动态规划那套来说就是状态转换方程：fn=fn-1+fn-2。先用递归：

  1. //递归
  2. int climb(int n){
  3.     if (n==1)
  4.         return 1;
  5.     if (n==2)
  6.         return 2;
  7.     return climb(n-1)+climb(n-2);
  8. }
  9. //IDE能过但是oj过不了
  12. //动态规划
  13. int climb2(int n){
  14.     if (n==1)
  15.         return 1;
  16.     vector<int>dp(n+1,0);
  17.     dp[1]=1;
  18.     dp[2]=2;
  19.     for (int i = 3; i < n+1; ++i) {
  20.         dp[i]=dp[i-1]+dp[i-2];
  21.     }
  22.     return dp[n];
  23. }
  26. //最终
  27. int climb3(int n){
  28.     int a = 1, b = 1, sum;
  29.     for(int i = 0; i < n; i++){
  30.         sum = (a + b) % 1000000007;
  31.         a = b;
  32.         b = sum;
  33.     }
  34.     return a;

最后发现其实也就是斐波那契数列

3.连续字数组最大和问题

继续，开工第三题。连续字数组最大和问题。自己在做的时候，失败了,备忘录的设定有问题。看了解析后发现是自己状态转换方程没有找正确。看懂后自己写了出来，提交成功，但是效率十分低，时间和空间都只是打败了百分之5的人，累了，先睡觉！。下面附上自己的代码：

  1. int maxSubArray(vector<int> &nums) {
  2.     int size=nums.size();
  3.     vector<int>dp(size);
  4.     dp[0]=nums[0];
  5.     for (int i = 1; i < size; ++i) {
  6.         if (dp[i-1]<0)
  7.             dp[i]=nums[i];
  8.         else
  9.             dp[i]=dp[i-1]+nums[i];
  10.     }
  11.     sort(dp.begin(),dp.end());
  12.     return dp[size-1];
  13. }

学习连续字数组最大问题更优的解法。更优的解法其实本质和昨天自己写的一样，唯一不同的是他定义了一个变量在遍历的时候就进行了比较，从而找出最大值，而我却只是生成了dp表，很笨的又进行了排序，取最值，很耗时间。没动脑子！

  1. int maxSubArray2(vector<int>& nums) {
  2.     int res = nums[0];
  3.     for(int i = 1; i < nums.size(); i++) {
  4.         if(nums[i - 1] > 0) nums[i] += nums[i - 1];
  5.         if(nums[i] > res) res = nums[i];
  6.     }
  7.     return res;
  8. }

4.礼物的最大价值

接着来，第四题。礼物的最大价值。动态规划，很简单 第(i.j)步的最大值就是i-1,j和i,j-1项比较大的礼物值和，加上第ij步的礼物值。设动态规划矩阵dp。做完后根据解析精简了代码：

  1. int maxValue(vector <vector<int>> &grid) {
  2.     int m = grid.size(), n = grid[0].size();//取矩阵的行和列
  3.     for (int i = 0; i < m; i++) {
  4.         for (int j = 0; j < n; j++) {
  5.             if (i == 0 && j == 0) 
  6.               continue;
  7.             if (i == 0) grid[i][j] += grid[i][j - 1];
  8.             else if (j == 0) grid[i][j] += grid[i - 1][j];
  9.             else grid[i][j] += max(grid[i][j - 1], grid[i - 1][j]);
  10.         }
  11.     }
  12.     return grid[m - 1][n - 1];
  13. }

5.最长不含重复字符的子字符串

前两天出去玩嘻嘻，今天开始！第五题：最长不含重复字符的子字符串。一下午扔进去，尝试了好久，没做出来。看解析后明白，在每一步的操作中，将左指针向右移动一格，表示开始枚举下一个字符作为起始位置，然后不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着以左指针开始的，不包含重复字符的最长子串。在判断重复字符时候，用到了哈希集合。其中发现一个问题：vector(128,0) 代替 unordered_map靠谱吗？

  1. int lengthOfLongestSubstring(string s) {
  2.     // 哈希集合，记录每个字符是否出现过
  3.     unordered_set<char> occ;
  4.     int n = s.size();
  5.     // 右指针，初始值为 -1、
  6.     int rk = -1, ans = 0;
  7.     // 枚举左指针的位置，初始值隐性地表示为 -1
  8.     for (int i = 0; i < n; ++i) {
  9.         if (i != 0) {
  10.             // 左指针向右移动一格，移除一个字符
  11.             occ.erase(s[i - 1]);
  12.         }
  13.         while (rk + 1 < n && !occ.count(s[rk + 1])) {
  14.             // 不断地移动右指针
  15.             occ.insert(s[rk + 1]);
  16.             ++rk;
  17.         }
  18.         ans = max(ans, rk - i + 1);
  19.     }
  20.     return ans;
  21. }

6.股票的最大利润

初看这道题，感觉一个dp备忘录即可解决，去试试。错了，状态转换方程错了，第一个测试案例都没过。看了解析发现是自己没有考虑当日卖出最大利润，而是写成了当日隔日卖出的利润。

  1. int maxProfit(vector<int>& prices) {
  2.     if (!prices.size())
  3.         return 0;
  4.     int maxVal = 0;
  5.     int Fiminus1 = 0, Fi = 0;
  6.     for (int i = 1; i <  prices.size(); i++) {
  7.         Fi = max(Fiminus1 + prices[i] - prices[i-1],  0);
  8.         maxVal = max(Fi, maxVal);
  9.         Fiminus1 = Fi;
  10.     }
  11.     return maxVal;
  12. }

翻看别的解析后发现了一种比较好玩的方法，使用栈去解决问题。
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/c-li-yong-shao-bing-wei-hu-yi-ge-dan-diao-zhan-tu-/。
之后看了优化后的代码，十分简练，作为学习也贴上来：

  1. int maxProfit(vector<int>& prices) {
  2.   int cost = INT_MAX, profit = 0;
  3.   for(int price : prices) {
  4.     cost = min(cost, price);
  5.     profit = max(profit, price - cost);
  6.   }
  7.   return profit;
  8. }

总结

动态规划的六个题都练完了，发现动态规划中找状态方程转换是最难的，很多时候没有考虑完全，导致错误频出。对于dp备忘录的使用还需要加强，而且很多时候可以进行空间上的优化，缩短至几个变量记录即可。这一点在之后的做题过程中多加注意，努力多用进去。