一些认识
递归本质上就是一种穷举，动态规划可以消除其中一些需要重复计算的子问题。所以从递归演进到动态规划一般是：递归 -> 递归+备忘录 -> 动态规划。一般来说，递归+备忘录的方法与动态规划的时间复杂度是相同的。
能用动态规划的条件就是，这个递归问题存在最优子结构，而且存在重复子问题，这时候只需要找出状态转移方程就可以求解动态规划问题。所以，最优子结构、重复子问题和状态转移方程也被称为动态规划问题的三要素。
回溯算法也是一种穷举，它通过适时地剪枝来节省运行时间。一般来说，如果一个递归的问题，要求最优解的大小，不需要知道得到最优解的路径，一般是使用动态规划便可以解决。而一些求最优的路径的时候，使用动态规划不能解决，这个时候需要用到回溯算法。
Leetcode 中，给出的动态规划与分治法、贪心法的比较：
分治
解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。 例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。 然后不断地对它们递归地进行处理。 这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候， 没有子问题重复出现，这是动态规划和分治的区别。
贪心
关于最优子结构
贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录 动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
关于子问题最优解组合成原问题最优解的组合方式
贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树 动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
结果正确性
贪心不能保证求得的最后解是最佳的，复杂度低 动态规划本质是穷举法，可以保证结果是最佳的，复杂度高
三者一起比较
分治 动态规划 贪心 适用类型 通用 优化 优化 子问题 每个都不同 有很多重复 只有一个 最优子结构 没有要求 必须满足 必须满足 子问题数 全部都要解 全部都要解 只解一个 可以看出来，动态规划提高速度的原因，是减少了重复子问题的计算，本质依旧是需要遍历所有的解。
DP数组滚动更新，经典的空间压缩
牛客网-程序员代码面试指南-矩阵的最小路径和-CD186
【难度】：⭐⭐
【自己解决的程度】：独立解决
本题不难，需要注意的点主要是通过滚动更新，将dp数组从O(m*n)压缩为O(min(m, n))。这一设计显著降低了空间复杂度，也减少了一次寻址的次数，从而也能提高运行速度。但因为滚动更新的时候，是覆盖之前的值，这就使得求解轨迹变得不可回溯。
int main(void){
int n, m;
cin >> n >> m;
cin.get(); // 别忘了吃掉这个回车
// 数据读入
vector<vector<int>> matrix(n, vector<int>(m));
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> matrix[i][j];
//开始计算
// 这里dp只有两行的原因是，这里的结果只与上一行的值有关
vector<int> dp (m, 0);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i == 0 && j == 0) dp[j] = matrix[i][j];
else if(i == 0 && j != 0)
dp[j] = dp[j-1] + matrix[i][j];
else if(i != 0 && j == 0)
dp[j] = dp[j] + matrix[i][j];
else dp[j] = min(dp[j], dp[j-1]) + matrix[i][j];
}
}
cout << dp[m-1];
return 0;
}
斐波那契数列
牛客网-程序员代码面试指南-斐波那契数列问题的递归和动态规划-CD183
【难度】：⭐⭐⭐⭐
【自己解决程度】：自己找到了与解答不同思路的解法
这个题使用暴力求解的话，时间复杂度为O(2^n)，如果使用动态规划求解的话，时间复杂度为O(n)。那么有没有时间复杂度为O(logn)的方法？书上解答给出了一种时间复杂度为O(logn)的方法，我自己想到了一种解决方法。先来看我想到的方法：
/*
* 这个题要找到时间复杂度为 O(logn)的方法
* 看到 O(logn)，自然想到的就是如何在每次计算的时候，都能将后续计算的规模缩小1(n)倍。
*
* 斐波那契数列的递推关系式展开，有
* fn = f(n-1) + f(n-2)
* = 2f(n-2) + f(n-3)
* = 3f(n-3) + 2f(n-4)
* 观察到，后面两项的系数，也都符合斐波那契数列
* 那是不是有这样的一个规律：
* 如果n为偶数：
* fn = f(4)f(n-3) + f(3)f(n-4)
* = ...
* = f(n/2)f(n/2+1) + f(n/2-1)f(n/2)
* 如果n为奇数：
* fn = f(4)f(n-3) + f(3)f(n-4)
* = ...
* = f(n/2+1)f(n/2+1) + f(n/2)f(n/2)
* 这样就成功地将所需要的时间缩小了一倍，中间f(n-1)到f(n/2+1)的值为多少我们都不关心了。
*/
代码如下：
const int Module = 1000000007;
unordered_map <long long, int> myhash;
int fib(long long n){
int arr [8] = {0, 1, 1, 2, 3, 5, 8, 13};
if(n < 8) return arr[(int)n];
if(myhash.find(n) != myhash.end()) return myhash[n];
long long temp;
if(n % 2 == 0) temp = fib(n/2)*(long long)(fib(n/2+1) + fib(n/2-1));
else temp = (long long)fib(n/2+1)*fib(n/2+1) + (long long)fib(n/2)*fib(n/2);
myhash[n] = (int)(temp % Module);
return (int)(temp % Module);
}
int main(void){
// 读入数据
long long n;
cin >> n;
cout << fib(n);
return 0;
}
书上的方法则更加具有普适性：
因为f(n) = f(n-1) + f(n-2)，所以，可以得到
(f(n), f(n-1)) = (f(n-1),f(n-2))*(1, 1)
(1, 0)
初始状态(f(2),f(1)) = (1, 1)，那么从初始状态求到n状态只需要做n-2变换，也就是乘上这个矩阵的n-2次方。而求矩阵的平方的时间复杂度是O(logn)，比如，求16次方就可以写成两个8次方的乘积；求19次方，因为二进制是10011，所以知道变换矩阵的16次方、2次方和1次方，便能求出。
下面的一个该题的变形，就用到了上面刚刚说到的方法。
牛客网-程序员代码面试指南-斐波那契数列问题的递归和动态规划3-CD186
【难度】：⭐⭐⭐⭐
【自己解决程度】：看完上题书中的的解法，也找到了本题的变换矩阵
本题与上题一样，也是要找到两次相邻状态之间的变换矩阵，思考过程如下：
/*
* 本题参考的是书上对斐波那契数列问题的解决方法
* 即找到两种状态之间转换的转换矩阵，然后通过矩阵乘法来求解
* 成熟母牛 三岁母牛 两岁母牛 一岁母牛
* 初始 n0: 1 0 0 0
* ...
* ni: a b c d
* ni+1: a+b c d a+b
* ...
* 从状态ni到状态ni+1的矩阵变换是：
* (a, b, c, d)( 1 0 0 1 ) = (a+b, c, d, a+b)
* ( 1 0 0 1 )
* ( 0 1 0 0 )
* ( 0 0 1 0 )
* 只需要求这个n次方，然后乘上初始向量，就可以得到最终的向量\
*
* 本题需要自己写一个矩阵乘法
*/
代码还需自己实现矩阵的乘法与矩阵的乘方，代码如下：
const int Module = 1000000007;
long long transMatrix [4][4] = { 1, 0, 0, 1,
1, 0, 0, 1,
0, 1, 0, 0,
0, 0, 1, 0 };
long long beginState [4][4] = { 1, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0 };
// 矩阵乘法，矩阵m1乘上矩阵m2
long long** MatrixMulti(long long ** m1, long long ** m2, int len){
long long** result = new long long* [len];
for(int i = 0; i < len; i++){
result[i] = new long long [len];
}
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
long long temp = 0;
for(int k = 0; k < len; k++){
temp += m1[i][k] * m2[k][j];
temp %= Module;
}
// 这里求一个余数，保证最后得到的结果都是在int范围内
result[i][j] = temp % Module;
}
}
return result;
}
// 矩阵乘方
long long** MatrixPower(long long n, long long ** matrix, int len){
// 先将result初始化为一个E矩阵
long long** result = new long long* [len];
for(int i = 0; i < len; i++){
result[i] = new long long [len];
for(int j = 0; j < len; j++){
if(i == j) result[i][j] = 1;
else result[i][j] = 0;
}
}
// 然后把n转二进制
vector<int> bN;
// 二进制低位在数组头
// 即 bN[0] 对应的是 2^0，bN[1]对应的是2^1
while(n > 0){
bN.push_back(n % 2);
n = n / 2;
}
for(int i = 0; i < bN.size(); i++){
if(bN[i] == 1) result = MatrixMulti(result, matrix, len);
matrix = MatrixMulti(matrix, matrix, len);
}
return result;
}
int main(void){
// 读入数据
long long n;
cin >> n;
// 初始化变换矩阵
int length = 4;
long long ** transform = new long long* [length];
for(int i = 0; i < length; i++){
transform[i] = transMatrix[i];
}
// 初始化初始状态
long long ** state = new long long* [length];
for(int i = 0; i < length; i++){
state[i] = beginState[i];
}
transform = MatrixPower(n-1, transform, length);
state = MatrixMulti(state, transform, length);
auto ans = (long long)(state[0][0] + state[0][1] + state[0][2] + state[0][3]);
cout << (int)(ans % Module);
return 0;
}
一些经典的动态规划题
Leetcode-72. 编辑距离
class Solution {
public:
int minDistance(string word1, string word2) {
// 始终保证word1的长度大于等于word2
if(word1.size() < word2.size()) swap(word1, word2);
int n1 = word1.size(), n2 = word2.size();
int delta = n1 - n2;
// 这里的dp矩阵的大小是否可以压缩？
vector<vector<int>> dp(n1+1, vector<int>(n2+1, -1));
for(int i = 0; i <= n2; i++){
// 以(i,i)为起点，先成一行，再生成一列
if(i == 0){
for(int j = 0; j <= n2; j++) dp[i][j] = j;
for(int j = 1; j <= n1; j++) dp[j][i] = j;
}
else{
for(int j = i; j <= n2; j++){
int a = dp[i-1][j-1] + (word1[i-1]==word2[j-1]? 0: 1);
int b = dp[i-1][j] + 1;
int c = dp[i][j-1] + 1;
dp[i][j] = min(a, min(b, c));
}
for(int j = i+1; j <= n1; j++){
int a = dp[j-1][i-1] + (word1[j-1]==word2[i-1]? 0: 1);
int b = dp[j][i-1] + 1;
int c = dp[j-1][i] + 1;
dp[j][i] = min(a, min(b, c));
}
}
}
return dp[n1][n2];
}
};
// 【思路】
//
// 一、dfs+记事本+剪枝
// 当在沿着word1往后走的时候，有两种情况：
// 1. 如果当前点与word2相同，word1和word2直接往后走一格
// 2. 如果当前点与word2不相同，
// 如果delta大于0，则可以选择word1往后走一格，delta-- 或者 记一次替换，word1和word2都往后走一格
// 如果delta等于0，则只能记一次替换，然后word1和word2都往后走一格。
// 为了减少重复计算，可以将word1[n1:]与word2[n2:]的结果记下来，且n1-n2 <= delta
// 中间过程也可以进行剪枝。
//
// 二、动态规划
// 根据上面得到的记事本，利用动态规划的思想，直接往后递推
// 例如：word1="horse", word2="ros"
// 第一个位置表示当前word1上的指针所指向的位置，第二个位置表示word2上的指针所指向的位置
// 第一列初始化
// (0,0)=0 [0,1] [0,2] [0,3]
// (1,0)=1 (1,1) [1,2] [1,3]
// (2,0)=2 (2,1) (2,2) [2,3]
// [3,0]=3 [3,1] (3,2) (3,3)
// [4,0]=4 [4,1] (4,2) (4,3)
// [5,0]=5 [5,1] [5,2] (5,3)
//
// f(a,b) = min(f(a-1,b)+1, f(a,b-1)+1, f(a-1, b-1)+(如果word1[a-1]==word2[b-1]，则为0；如果!=，则加1), )
// 上面的转移方程表述的其实是三种情况，一种是从word1上删掉了一个，一种是从word2上删掉一个，一种是判断是否交换一个
// 一开始只想到了上面的第一种和第三种情况，得到的dp矩阵是上面矩阵中用小括号填充的部分
// 遇到反例：
// "sea" "eat" result=2
牛客网-程序员代码面试指南-换钱的方法数-CD19⭐⭐
【难度】：⭐⭐
【自己解决程度】：看了一下题解说要列一张N*aim大小的表之后才有思路
这个题是做动态规划题目以来遇到的最难的一道题目，个人感觉应该是⭐⭐⭐的难度。
“这道题的经典之处在于，它可以体现暴力递归、记忆搜索和动态规划之间的关系，并可以在动态规划的基础上进行再一次优化”
【时间复杂度O(N*aim)但是错误的方法】
我一开始想到的方法是题目牛客网-程序员代码面试指南-换钱的最少货币数-CD12中给出的方法，这里使用这一方法来做，会难以消除重复解的问题。比如：货币的面值为1、3、5，想要找到面值之和为8的货币，我的这个算法可能会将先拿3再拿5凑齐8元 与 先拿5再拿3凑齐8元视为是同一种情况。
【时间复杂度O(N*aim*aim)的方法】
可以依次换，比如，现在有面值为a、b、c的货币。然后先把能用a换到的数额都置为1，之后就不再关心面值为a的钱了，然后以每个数字开始i，就可以求 b的倍数 nb，dp[i+nb]++。对于面值为c的钱也是同样。
【时间复杂度O(N*aim)的方法】
需要使用一张大小为N*aim的表来记录上述过程：
例如：现在手里有面值为1、3、5的货币，想要求有几种方法可以得到8元。
-
详细表格：
0 1 2 3 4 5 6 7 8 1 1x1 2x1 3x1 4x1 1x3+1 5x1 1x3+2x1 6x1 1x3+3x1 1x5+1 7x1 1x3+4x1 1x5+2x1 2x3+1 8x1 1x3+5x1 1x5+3x1 2x3+2x1 3 1x3 2x3 1x5+3 5 1x5 列表示对应货币的面值，行表示当前的金额。可以看到，维持一种增加货币的顺序，就可以保证不出现重复的情况。
-
对上表进行化简：
0 1 2 3 4 5 6 7 8 1 0 1 1 1 2 2 3 4 4 3 0 0 0 1 0 0 1 0 1 5 0 0 0 0 0 1 0 0 0 在数额为
i处新增一张货币j，就把dp[i-j][j]~dp[i-j][n]的数额都加到dp[i][j]上。这样便维持上面所说的顺序。但这里将dp[i-j][j]~dp[i-j][n]加到dp[i][j]之上的这一过程，要花费O(n)的时间复杂度，总的时间复杂度为O(n*n*aim)。说明还可以继续改进。 -
优化时间复杂度：
上面可以看到，只需在
dp[i][j]能够知道dp[i][j]~dp[i][n]的和就可以了，这个不难做到，只需要在给dp赋值的时候，记录一个累加值，从而避免了每次枚举再累加。0 1 2 3 4 5 6 7 8 arr[0]=1 0 1 1 2 2 3 4 4 5 arr[1]=3 0 0 0 1 0 1 1 0 1 arr[2]=5 0 0 0 0 0 1 0 0 0 dp[i][j]中放的是dp[i][j]~dp[i][n]的解的总数。dp[i][j]-dp[i][j+1]才是真正的这个位置新得到的解的个数。
代码如下：
const int Module = 1000000007;
int main(void){
// 读入数据
int n, aim;
cin >> n >> aim;
cin.get();
vector<int> arr(n);
for(int i = 0; i < n; i++){
cin >> arr[i];
}
// 开始计算
// 用一个大小为 n x aim 的二维数组来存储
vector<vector<int>> dp (aim+1, vector<int>(n, 0));
for(int i = 0; i <= aim; i++){
int sum = 0;
for(int j = n-1; j >= 0; j--){
int delta = i - arr[j];
if(delta == 0) sum += 1;
else if(delta > 0){
sum += dp[delta][j];
sum %= Module;
}
dp[i][j] = sum;
}
}
cout << dp[aim][0];
return 0;
}
【书上的解法】
书上的解法总体上与我的优化思路相似，但是给出了一些更加宏观的认识。
书上指出记忆搜索方法在本质上等价于动态规划方法，两者都是用空间换时间，记忆搜索方法还是使用的递归，只是将一些已经计算过的解记录了下来，避免了重复计算。而动态规划则是规定好每一个递归过程的计算顺序，依次进行计算，后面的计算过程严格依赖前面计算的过程。
而且书上的方法是容易进行空间压缩的，而我的方法则不容易做到。
牛客网-程序员面试代码指南-打气球的最大分数-CD20⭐⭐⭐
【难度】：⭐⭐⭐
【自己完成程度】：没有思路，跟着书上的解法完成
int main(void){
// 读入数据
int n;
cin >> n;
cin.get();
vector<int> arr(n);
for(int i = 0; i < n; i++){
cin >> arr[i];
}
// 开始计算
// 新构建的帮助数组，前后分别填充 1以方便计算
vector<int> help;
help.push_back(1);
for(int a : arr) help.push_back(a);
help.push_back(1);
// 构建的一个dp矩阵，大小为 (n+2)x(n+2)，初始化为全 0
// dp[l][r]表示，当 l-1 和 r+1 都没有被打爆的时候，打爆 [l,r]之间的所有的气球的得分
vector<vector<int>> dp (n+2, vector<int>(n+2, 0));
// 沿一列列对角线循环求解
for(int i = 0; i < n; i++){
for(int l = 1; l <= n-i; l++){
int r = l + i;
if(i == 0) dp[l][r] = help[l-1]*help[l]*help[l+1];
else{
vector<int> temp; // 暂存可能解，用来找最优解
// 假设第 k个球最后被打爆
for(int k = l; k <= r; k++) {
int val = dp[l][k - 1] + help[l - 1] * help[k] * help[r + 1] + dp[k + 1][r];
temp.push_back(val);
}
dp[l][r] = *max_element(temp.begin(), temp.end());
}
}
}
cout << dp[1][n];
return 0;
}
【小结】：
0-1背包问题
Leetcode 416.分割等和子集
// 本题是一道典型的0-1背包问题，0-1背包问题是一个NP完全问题
// 可以这样来思考，我们要找到两个子集的元素和相等，就相当于找到一个子集，它的元素和为总的元素和的一半
// 这就转化成一个0-1背包问题，已知背包的容量，每个物品只有一个，只能选择拿与不拿
// 问如何拿取物品刚好填满这个背包
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int n : nums) sum += n;
// 先解决一些显而易见的情况
if(sum % 2 == 1) return false;
// 开始计算
int target = sum / 2;
vector<int> dp (target + 1, 0);
// base case
dp[0] = 1;
// other case
for(int num : nums){
vector <int> vec;
for(int i = 0; i <= target; i++){
if(dp[i] == 1 && i + num <= target){
if(i+num == target) return true;
else vec.push_back(i+num);
}
}
// 这里需要等前面计算完了再更新
// 或者也可以将上面的i，改为从target遍历到0，这样就能保证更新顺序
for(int v : vec) dp[v] = 1;
}
return false;
}
};
这个题可以这样来考虑，在[1,n] 区间内是否可以取出一个子数组，使得它们的和为target，我们可以记为 f(1, n, target) ，当f值为1的时候，表示存在这样的一个子数组，当f值为0的时候，表示不存在这样的一个子数组。那么，f(1, n, target) = max{f(1, n-1, target), f(1, n-1, target-arr[n])}，即，如果不取元素arr[n]（元素从1开始编号），加和已经为target的话，则就不取。如果不取，得不到，但是取了arr[n]加和为target，也算得到。其他情况均不算能得到。
那么我们其实不关心前面到底取了谁没取谁，只关心当前轮到第i个元素的时候，它的取和不取，会给当前的情况带来那些新的总和。
Leetcode 518.零钱兑换 II
我的解法，与牛客网换钱的方法数CD19其实是同一个题。
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
if(amount == 0) return 1;
if(n == 0) return 0;
vector<vector<int>> dp (n, vector<int>(amount+1, 0));
// sort(coins.begin(), coins.end());
// base case:
// 这里的base case有问题，因为dp[j][i]被我设置为一个累加值
// 所以既不能全为1，也不能累加，所以就直接在循环体中做累加1这一操作了
// other case:
for(int i = 1; i <= amount; i++){
// dp[j][i]中存的是一个累计值，累计dp[j][i]到dp[n-1][i]
int a = 0;
for(int j = n-1; j >= 0; j--){
int delta = i - coins[j];
if(delta == 0) a += 1;
else if(delta > 0) a += dp[j][delta];
dp[j][i] = a;
}
}
return dp[0][amount];
}
};
labuladong 给出的另外一种更好的方法，而且可以对时间复杂度进行压缩：
// 另外的一种更直观的做法
// 用dp[i][j] 表示，只使用coins[0]到coins[i]，来得到数额j
class Solution {
public:
int change(int amount, vector<int>& coins){
int n = coins.size();
if(amount == 0) return 1;
if(n == 0) return 0;
vector<vector<int>> dp (n+1, vector<int>(amount+1, 0));
// base case:
for(int i = 0; i < n; i++) dp[i][0] = 1;
// post case:
for(int i = 0; i < n; i++){
for(int j = 1; j <= amount; j++){
int delta1 = 0, delta2 = 0;
if(j - coins[i] >= 0) delta1 = dp[i][j-coins[i]];
if(i-1 >= 0) delta2 = dp[i-1][j];
dp[i][j] = delta1 + delta2;
}
}
return dp[n-1][amount];
}
};
Leetcode 474.一和零
// 0-1背包问题
// 每个元素只有取和不取两种情况
// 依次考虑strs中的元素
// 无论是取还是不取，都是在之前所有的状态下，增加自己的这个状态
// dp的大小为[strs.size()][m]
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
vector<int> help (len+1, 0);
vector<vector<int>> dp (len+1, vector<int>(m+1, -1));
// base case:
help[0] = 1;
dp[0][0] = 0;
// other case:
for(int i = 0; i < len; i++){
// cout << "i=" << i << ", ";
int zeroCt = 0, oneCt = 0;
for(char c : strs[i]){
if(c == '0') zeroCt++;
else oneCt++;
}
for(int j = i; j >= 0; j--){
if(help[j] == 1){
for(int k = 0; k <= m; k++){
if(dp[j][k] == -1) continue;
int zeroCtNew = zeroCt + k;
int oneCtNew = oneCt + dp[j][k];
if(zeroCtNew <= m && oneCtNew <= n &&
(dp[j+1][zeroCtNew] == -1
|| dp[j+1][zeroCtNew] > oneCtNew)){
dp[j+1][zeroCtNew] = oneCtNew;
help[j+1] = 1;
}
}
}
}
}
// 返回结果
int res = 0;
for(int j = 0; j <= len; j++) if(help[j] == 1) res = j;
return res;
}
};
其他的动态规划题
Leetcode-1770. 执行乘法运算的最大分数
本题是一道周赛题，当时在做的时候，没有想出来思路。本题如果直接使用暴力方法递归求解的话，每次都可以从nums的前面或者后面选取一个与multipliers的一个数字相乘，就会有两条分支，所以，总的时间复杂度为 $2^{m-1}$ 这个数量级，显然会超时。考虑使用动态规划来求解，
class Solution {
public:
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int m = multipliers.size(), n = nums.size();
int result = INT_MIN;
vector<vector<int>> dp (m, vector<int>(m, 0));
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
if(i == 0 && j == 0) continue;
else if(i == 0){
dp[i][j] = dp[i][j-1] + multipliers[i+j-1]*nums[n-j];
}
else if(j == 0){
dp[i][j] = dp[i-1][j] + multipliers[i+j-1]*nums[i-1];
}
else{
int a = dp[i-1][j] + multipliers[i+j-1]*nums[i-1];
int b = dp[i][j-1] + multipliers[i+j-1]*nums[n-j];
dp[i][j] = max(a, b);
}
if(i+j == m){
if(dp[i][j] > result) result = dp[i][j];
break;
}
}
}
return result;
}
};
Leetcode-53. 最大子序和
这道题遇到过好几次，都没做出来。这是一道比较经典的动态规划题。
$f(i)$代表从$0$到 $i$ 的子数组中，最大值的大小。状态转移方程为： \(f(i) = max(nums[i], nums[i]+f(i-1))\) 即取 $nums[i]$ 和 $nums[i]+f(i-1)$ 中的最大值。
这个道理很容易理解，如果前i个的最大值还没有第i个大，那么此时的最大值就取第i个。
我自己的思路把这个问题搞复杂了，我一开始想要分开讨论，我也是建设前i个的最大值是$f(i)$，但是我将其分成了两种情况，一种是最大值的末尾刚好就是区间末尾，一种是最大值的末尾不是区间末尾。这确实是一种描述方式，但是不容易得到$f(i+1)$。
那么如何从题目中得到答案中的这种思路呢？
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0], sum = nums[0];
for(int i = 1; i < nums.size(); i++){
sum = max(nums[i], sum + nums[i]);
if(sum > res) res = sum;
}
return res;
}
};
198. 打家劫舍
我的做法：
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size(), res = 0;
if(len == 0) return res;
vector<vector<int>> dp(len, vector<int>(2, 0));
// 这里dp[i][0]表示不偷，dp[i][1]表示要偷
dp[0][0] = 0;
dp[0][1] = nums[0];
res = nums[0];
for(int i = 1; i < len; i++){
// 不偷的情况
if(i >= 2) dp[i][0] = max(dp[i-1][1], dp[i-2][1]);
else dp[i][0] = dp[i-1][1];
// 偷的情况
if(i >= 2) dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + nums[i];
else dp[i][1] = dp[i-1][0] + nums[i];
// 更新结果
if(res < dp[i][0]) res = dp[i][0];
if(res < dp[i][1]) res = dp[i][1];
}
return res;
}
};
我的方法复杂度，没问题，也是动态规划，但是比答案的方法稍微麻烦了一点。