算法：动态规划-易微帮

开始前先用两个小问题开开思路：

寻找多数元素：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
};

这是一个投票的算法，x代表候选者，votes代表票数，当votes等于0就说明要更换新的候选者了，在候选者遍历的期间，它会根据与当前元素是否相同，进行累加或者减少，最终得到的候选者（没有被归0或者代替的），就是数组中存在最多次数的元素。

寻找公共前缀：

链接：题目2

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        int length = strs[0].size();
        int count = strs.size();
        for (int i = 0; i < length; ++i) {
            char c = strs[0][i];
            for (int j = 1; j < count; ++j) {
                if (i == strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};

动态规划

扩宽一下你的思路,主要是学习他怎么避免重复求解，什么样的问题用动态规划，以及怎么做，提高运行效率的。

动态规划（Dynamic Programming, DP）在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。

因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间 · · · · · · 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。”

通俗一点来讲，动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问
题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规
划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。

动态规划的核心思想：

1.把「原问题」分解为「若干个重叠的子问题」，每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后，动态规划方法才会执行下一个阶段的计算。
2.在求解子问题的过程中，按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」，把结果存储在表格中，当需要再次求解此子问题时，直接从表格中查询该子问题的解，从而避免了大量的重复计算。

这看起来很像是分治算法，但动态规划与分治算法的不同点在于：（有重叠和无重叠）

1.适用于动态规划求解的问题，在分解之后得到的子问题往往是相互联系的，会出现若干个重叠子问题。

2.使用动态规划方法会将这些重叠子问题的解保存到表格里，供随后的计算查询使用，从而避免大量的重复计算。

在本节中，我们从一个经典例题入手，先给出它的暴力回溯解法，观察其中包含的重叠子问题，再逐步导出更高效的动态规划解法。

给定一个共有n 阶的楼梯，你每步可以上1阶或者2阶，请问有多少种方案可以爬到楼顶。

本题的目标是求解方案数量，我们可以考虑通过回溯来穷举所有可能性。具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上1阶或2阶，每当到达楼梯顶部时就将方案数量加1 ，当越过楼梯顶部时就将其剪枝。

#include <stdio.h>  
#include <stdlib.h>  
  
void backtrack(int *choices, int state, int n, int *res) {  
    if (state == n) {  
        (*res)++;  
        return;  
    }  
  
    for (int i = 0; i < 2; i++) {  
        int choice = choices[i];  
        if (state + choice > n) {  
            break;  
        }  
        backtrack(choices, state + choice, n, res);  
    }  
}  
  
int climbingStairsBacktrack(int n) {  
    int choices[2] = {1, 2};  
    int state = 0;  
    int res = 0; // 直接使用整数变量来记录方案数量  
  
    backtrack(choices, state, n, &res);  
  
    return res;  
}  
  
int main() {  
    int n = 3; // 举例：5阶楼梯  
    int result = climbingStairsBacktrack(n);  
    printf(" %d 阶楼梯有 %d种方法\n", n, result);  
    return 0;  
}

暴力搜索

这是一个很暴力的求法，直接去不断调用可能的结果求解。

回溯算法通常并不显式地对问题进行拆解，而是将问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。我们可以尝试从问题分解的角度分析这道题。设爬到第i 阶共有dp[i] 种方案，那么dp[i]就是原问题，其子问题包括:

dp[i-1],dp[i-2],...,dp[2],dp[1]

由于每轮只能上1阶或2阶，因此当我们站在第i 阶楼梯上时，上一轮只可能站在第 i-1 阶或第 i-2 阶上。换句话说，我们只能从第 i-1阶或第 i-2阶前往第 i 阶。

由此便可得出一个重要推论：爬到第 i-1 阶的方案数加上爬到第 i-2 阶的方案数就等于爬到第 i 阶的方案数。公式如下：

dp[i] = dp[i-1] +dp[i-2]

这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。下图展示了该递推关系。（像下面的代码它就存储了每次运算后的结果，方便后面的调用，实现了时间复杂度的优化，由于它是从顶到低的因此是记忆化搜索）

#include <stdio.h>  
#include <stdlib.h>  
  
// 假设最大楼梯数不会超过某个值 MAX_STAIRS  
#define MAX_STAIRS 100  
int memo[MAX_STAIRS + 1] = {0}; // 初始化记忆化数组为0  
  
int dfs(int i) {  
    // 已知 dp[1] 和 dp[2] ，返回之  
    if (i == 1) return 1;  
    if (i == 2) return 2;  
    // 如果已经计算过，则直接返回结果  
    if (memo[i] != 0) return memo[i];  
    // dp[i] = dp[i-1] + dp[i-2]  
    int count = dfs(i - 1) + dfs(i - 2);  
    // 将结果存入记忆化数组  
    memo[i] = count;  
    return count;  
}  
  
/* 爬楼梯：搜索（带记忆化） */  
int climbingStairsDFS(int n) {  
    return dfs(n);  
}  
  
int main() {  
    int n = 5; // 举例：计算到达第10阶楼梯的方法数  
    int result = climbingStairsDFS(n);  
    printf(" %d 阶楼梯有 %d种方法\n", n, result);  
    return 0;  
}

记忆化搜索

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。为此，我们声明一个数组 mem 来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝。

1. 当首次计算dp[i] 时，我们将其记录至 mem0[i] ，以便之后使用。

2. 当再次需要计算dp[i] 时，我们便可直接从 mem0[i] 中获取结果，从而避免重复计算该子问题。

当然上面的代码是一个全局的存储，你也可以用局部的存储方式，不过那要开辟空间释放资源，比全局更加高效点。

经过记忆化处理后，所有重叠子问题都只需被计算一次，时间复杂度被优化至 O(n) ，这是一个巨大的飞跃。

动态规划搜索

下面展示动态规划，它是从低到顶的，而且不需要递归。直接暴力存储的分问题求解。

记忆化搜索是一种“从顶至底”的方法：我们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯将子问题的解逐层收集，构建出原问题的解。

与之相反，动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。在以下代码中，我们初始化一个数组 dp 来存储子问题的解，它起到了记忆化搜索中数组 mem 相同的记录作用。

#include <stdio.h>  
#include <stdlib.h>  
  
// 爬楼梯：动态规划  
int climbingStairsDP(int n) {  
    if (n == 1 || n == 2)  
        return n;  
    // 初始化 dp 表，用于存储子问题的解  
    int *dp = (int *)malloc((n + 1) * sizeof(int));  
    if (dp == NULL) {  
        // 处理内存分配失败的情况  
        perror("Memory allocation failed");  
        exit(EXIT_FAILURE);  
    }  
    // 初始状态：预设最小子问题的解  
    dp[1] = 1;  
    dp[2] = 2;  
    // 状态转移：从较小子问题逐步求解较大子问题  
    for (int i = 3; i <= n; i++) {  
        dp[i] = dp[i - 1] + dp[i - 2];  
    }  
    int result = dp[n];  
    // 释放内存  
    free(dp);  
    return result;  
}  
  
int main() {  
    int n = 5; // 举例：计算到达第10阶楼梯的方法数  
    int result = climbingStairsDP(n);  
    printf("到达 %d 阶楼梯有 %d 种方法\n", n, result);  
    return 0;  
}

为什么可以采用：dp[i] = dp[i - 1] + dp[i - 2]; 因为本题是走一步或者两步的情况，对于dp[5]=dp[3]+dp[4]。也就是说对于5层阶梯的情况，可以分为两个子问题,到第3层走2步，到第4层走1步，因为这一步对于走到第几层来说，再继续走一次方法的个数是不变的。

就好比你从学校到家楼下有4种方式，那你上楼到家是不悔影响从学校到家楼下的方式数量的，因此从学校到家里面也是4种方式。

与回溯算法一样，动态规划也使用“状态”概念来表示问题求解的某个特定阶段，每个状态都对应一个子问题以及相应的局部最优解。例如，爬楼梯问题的状态定义为当前所在楼梯阶数i。

根据以上内容，我们可以总结出动态规划的常用术语。

将数组 dp 称为「dp表」，dp[i]表示状态i 对应子问题的解。
将最小子问题对应的状态（即第1 和2 阶楼梯）称为「初始状态」。
将递推公式 dp[i] = dp[i-1]+dp[i-2]称为「状态转移方程」。
1. 细心的你可能发现，由于dp[i]只与dp[i-1] 和dp[i-2] 有关，因此我们无须使用一个数组 dp 来存储所有子问题的解，而只需两个变量滚动前进即可。（是的，它又又又优化了，厉不厉害！）

优化

#include <stdio.h>  
  
// 爬楼梯：空间优化后的动态规划  
int climbingStairsDPComp(int n) {  
    if (n == 1 || n == 2)  
        return n;  
    int a = 1, b = 2;  
    for (int i = 3; i <= n; i++) {  
        int tmp = b;  
        b = a + b;  
        a = tmp;  
    }  
    return b;  
}  
  
int main() {  
    int n = 10; // 举例：计算到达第10阶楼梯的方法数  
    int result = climbingStairsDPComp(n);  
    printf("到达 %d 阶楼梯有 %d 种方法\n", n, result);  
    return 0;  
}

观察以上代码，由于省去了数组 dp 占用的空间，因此空间复杂度从 O(n)降低至 O(1) 。

在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时我们可以只保留必要的状态，通过“降维”来节省内存空间。这种空间优化技巧被称为“滚动变量”或“滚动数组”。