动态规划

注：此处不能使用贪心进行求解，贪心的思想为：在给定的价格数组中，寻找单调增区间，选取两个区间宽度最大的单调增区间，两个区间的宽度的相加就是最大利润，也可能不存在这样的两个或一个区间。但是对于数组 [1,2,4,2,5,7,2,4,9,0] ，此时贪心求解的值为12，但实际的最大利润为13。

基于动态规划实现：重点依旧是动态规划数组的定义和推导。（此处的定义，使用的是持有，也就是不关系具体是在那一天进行买卖，也就是关心的是在某一天是否拥有股票）

1. 动态规划数组得到定义：定义数组 dp[n][5] ，那么数组的含义为：

• dp[i][0] 表示在第 i 天不对股票进行操作所拥有的最大现金数
• dp[i][1] 表示在第 i 天第一次持有股票所拥有的最大现金数
• dp[i][2] 表示在第 i 天第一次不持有股票所拥有的最大现金数
• dp[i][3] 表示在第 i 天第二次持有股票所拥有的最大现金数
• dp[i][4] 表示在第 i 天第二次不持有股票所拥有的最大现金数

1. 动态规划数组的推导：在第 i 天需要对5个状态进行推导。

• dp[i][0]=0
• dp[i][1] 此处有两种情况：第一，是在第 i 天买入的 =dp[i-1][0]-prices[i] ，第二是在之前买入的 =dp[i-1][1] ，所以 dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][1])
• dp[i][2] 也有两种情况：第一，是在第 i 天卖出的 =dp[i-1][1]+prices[i] ，第二是在之前卖出的 =dp[i-1][2] ， 所以 dp[i][2]=max(dp[i-1][1]+prices[i],dp[i-1][2])
• dp[i][3] 此处有两种情况：第一，是在第 i 天买入的 =dp[i-1][2]-prices[i] ，第二是在之前买入的 =dp[i-1][3] ，所以 dp[i][3]=max(dp[i-1][2]-prices[i],dp[i-1][3])
• dp[i][2] 也有两种情况：第一，是在第 i 天卖出的 =dp[i-1][3]+prices[i] ，第二是在之前卖出的 =dp[i-1][4] ， 所以 dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4])

1. 动态规划数组的初始化：此处主要是对第 0 天进行初始化，不操作 dp[0][0]=0 ，那么在第 0 天第一次持有 dp[0][1]=-prices[0] 在第 0 天第一次不持有，本质上就是买入后当天卖出 dp[0][2]=0 ，那么同理第二次持有和不持有的情形，也是当天买入后，当天卖出 dp[0][3]=-prices[0],dp[0][4]=0

2. 动态规划数组的遍历：从前向后遍历的方式

3. 举例验证：对于数组 prices = [3,3,5,0,0,3,1,4] ，对应的动态规划数组为：

0 ,-3 , 0 ,-3 , 0 ,
0 ,-3 , 0 ,-3 , 0 ,
0 ,-3 , 2 ,-3 , 2 ,
0 , 0 , 2 , 2 , 2 ,
0 , 0 , 2 , 2 , 2 ,
0 , 0 , 3 , 2 , 5 ,
0 , 0 , 3 , 2 , 5 ,
0 , 0 , 4 , 2 , 6 ,

贪心

相较于121.买卖股票的最佳时机，本题的主要区别在于：考虑的不只是单次买卖股票的情形，可以对一只股票多次进行买卖，需要求解的是整体的最优化。

要想实现最大的利润，那么本质上就是在序列中寻找单调区间，将序列中的全部单调增区间的区间长度相加，就是最大的利润值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1) return 0;
        int start=prices[0],last=start;
        int res=0;
        for(int i=1;i<n;i++){
            if(prices[i]>=last){
                last=prices[i];
            }else{
                res+=last-start;
                start=prices[i];
                last=start;
            }
        }
        res+=last-start;
        return res;
    }
};

更加高效的贪心实现：在本题中，交易的次数是不存在限制的，因此完全可以采取如下策略。

对于 i 和 i-1 只要 prices[i]>prices[i-1] 那么就在 i-1 买入，在 i 天卖出，也就是赚取全部能够赚取的利润。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1) return 0;
        int res=0;
        for(int i=1;i<n;i++){
            res+=max(0,prices[i]-prices[i-1]);
        }
        return res;
    }
};

动态规划

本题的重点在于递推关系的确定，此处只考虑买入时间，不考虑卖出时间（本质上卖出时间就是最大利润的那一天）：第 i 天买入，能够获得最大利润使用 dp[i] 表示，那么第 i+1 天买入能够获得的最大利润使用 dp[i+1] 表示，那么 dp[i]=max(dp[i+1]+(prices[i]-prices[i-1]),0) ，那么使用动态规划进行求解的过程为：

1. 动态规划数组的定义：定义数组 dp[n+1] 表示第 n 天买入能够获得的最大利润

2. 动态规划数组的推导： dp[i]=max(dp[i+1]+(prices[i]-prices[i-1]),0)

3. 动态规划数组的初始化：对于最后一天买入的股票，必然不能盈利那么 dp[n+1]=0

4. 动态规划数组的遍历顺序：在计算 dp[n] 时需要使用 dp[n+1] 的信息，因此此处需要使用从后向前遍历的方式。

5. 对于 vector<int> prices={7,1,5,3,6,4}; 动态规划数组的输出为： dp=[0,0,3,1,5,0] 验证正确

深度优先

改变了相邻节点的定义：此处是在一棵二叉树中进行节点的选取，使得节点的和值最大，那么从父节点开始遍历，选取了父节点就不能选取子节点。

暴力搜索实现：遍历每一种合法的选取情形，判断能够选取到的最大值。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int robTree(TreeNode* root){ // 计算对于以root为根节点能够抢到的最大的值
        if(root){ // 当前节点非空
            if(!root->left&&!root->right) return root->val;
            int val1=root->val;
            if(root->left) val1+=(robTree(root->left->left)+robTree(root->left->right));
            if(root->right) val1+=(robTree(root->right->left)+robTree(root->right->right));
            int val2=robTree(root->left)+robTree(root->right);
            return max(val1,val2);
        }
        return 0;
    }
    int rob(TreeNode* root) {
        return robTree(root);
    }
};

这样的实现方式，本质上是在进行穷举，不断尝试选取方案，类似于是回溯的方法实现，在LeetCode的测试用例中将会超出时间限制。

记忆化搜索：在上述的计算过程中存在较多的重复计算。比如在计算 robTree(root->left) 的时候就重复计算了 (robTree(root->left->left)+robTree(root->left->right)) ，使用一个map记录计算的过程，从而减少计算。此处在基于记忆化搜索时，有一个非常需要注意的点：使用一个Map进行记录，那么对于正在寻找最大值的当前节点，在开始遍历前，尝试访问map中的数据，若是访问成功，那么本次求解直接结束（在非空和非叶子节点的情形下），若是访问失败，那么按照正常的遍历方式去进行DFS，在本次访问返回前将相应的数值存储在map中。

动态规划

本题相较于198.打家劫舍的主要区别在于，首尾的元素也成了相邻元素，导致元素成为了一个环，因此不能采取前面的方式计算。

此处可以将问题进行转化：此处的首尾元素只有一个可以被选取，那么将问题划分为两部分。

1. 不选取首元素，那么此时尾元素就可以选取，问题转化为在后n-1个元素不相邻选取最大值，求得res1
2. 不选取尾元素，那么此时首元素就可以选取，问题转化为在前n-1个元素不相邻选取最大值，求得res2

在得到res1和res2后，只需要选取其中较大的即可，在此基础上，使用动态规划求解：

1. 动态规划数组的定义：定义数组 dp[i] 表示在 0-i 的元素中选取，能够得到的最大值

2. 动态规划数组的推导：不选取当前元素 i 那么 i-1 是可以被选取(不代表一定选取)，选取当前元素 i 那么 i-1 不可选取，从 dp[i-2] 计算 dp[i]=max(dp[i-1],dp[i-2]+nums[i])

3. 动态规划数组的初始化：对于情况2 dp[0]=nums[0],dp[1]=max(nums[0],nums[1]) ，对于情况1 dp[0]=nums[1],dp[1]=max(nums[1],nums[2])

4. 动态规划数组的遍历顺序：需要使用前面的两个元素，从前向后遍历

5. 举例验证：对于 nums=[2,3,2] 输出结果为 3 ，验证正确

动态规划

此处是一个非常明显的动态规划问题，在物品的选取上，主要的限制在于不能选取两个相邻的物品，在此条件下实现物品价值的最大化。

1. 动态规划数组的定义：定义数组 dp[nums.size()+1] 表示在 nums.size() 个物品中进行选取能够得到的最大的物品价值。

2. 动态规划数组的推导：在 j 个物品中选取，可以选取第 j 个物品也可以不进行选取，那么 dp[j]=max(dp[j-1],dp[j-2]+nums[j-1])

3. 动态规划数组的初始化：对于 dp[0] 不存在可选元素， dp[0]=0 ，对于 dp[1] 只能选取第一个元素 dp[1]=nums[0]

4. 动态规划数组的遍历顺序：在递推的过程中使用到的前面的数据，因此从前向后遍历。

5. 举例验证：对于 nums=[1,2,3,1]

dp={0,1,0,0,0}
dp={0,1,2,0,0}
dp={0,1,2,4,0}
dp={0,1,2,4,4}

完全背包问题总结

首先，需要清楚的是对于完全背包问题的定义：有N件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

相较于0/1背包问题，完全背包问题最大的不同之处在物品的个数是无限。那么在进行选择时，就是每一次向背包中添加物品时，都有 n 个物品可供选择（即从所有的物品中做任意的选择）。

完全背包问题的实现只需要在0/1背包的基础上稍作改动即可，依旧是采取滚动数组实现。

1. 对于先便利物品，再遍历背包的情形：那么完全背包相较于0/1背包的不同之处，在第 i 次迭代时，0/1背包只能使用一次物品 weight[i] ，因此采取从后向前的方式遍历，为了防止重复选择，但是完全背包可以使用任意次物品 weight[i] ，所以需要实现重复的选取，因此采取从前向后的遍历方式即可。并且这种先遍历物品再遍历背包的方式，本质上是在求解组合问题，也就是对于物品的选取顺序是不敏感的，仅对物品的个数敏感。（因为先遍历物品，因此也就确定了选取的顺序）

2. 先遍历背包，再遍历物品：也就是对于每一种情形下的背包容量，都从全部的物品中进行选择。在单纯的完全背包问题下，递推公式和结果是不会改变的。但是这样的遍历方式，本质上是在求解排列问题，也就是对于物品的选取顺序是敏感的，因为先遍历的是背包容量，在背包容量增大的过程中，最后一次选取的物品不同将会是不同的情形。

动态规划

将问题转化为完全背包问题：此处的背包问题并不是求解最优化，而是判断能否将背包装满。但是此处的背包不同于之前的背包，背包中装入的必须是特定的元素。

此处需要判断的是能否恰好装满，若是先遍历物品，再遍历背包，那么实际上限制了物品元素的使用。（本质上是一个排列问题，元素在背包中有序）

考虑这样一种情况： s="applepenapple" wordDict=["apple","pen"] 那么先遍历物品，再遍历背包，初始时只能使用 apple 那么只能将第一个 apple 恰好装满，在第二次迭代中，是只考虑增加 pen 的情形，但实际上还需要使用 apple 对尾部进行装填，也就是每次向背包中装入时，需要使用到全部的物品，所以应该先遍历背包再遍历物品。

1. 动态规划数组的定义：定义数组 dp[s.size()+1] 表示长度为 s.size() 的字符串能否恰好装满

2. 动态规划数组的推导：在第 j 次迭代中，判断字符从 0-j-1 位置的字符串 s 能否恰好装满，对于每一个物品 wordDict[i] 都需要尝试从 j-1 处向前装入试试，所以有：其中 match 是字符串匹配操作。

1
2
3

if(j>=wordDict[i].size()){
    dp[j]=dp[j]||(dp[j-wordDict[i].size()]&&match(s,j-1,wordDict[i]));
}

1. 动态规划数组的初始化：对于dp[0] 一定是能够恰好装满的，所以 dp[0]=true 其他全部初始化为 false

2. 动态规划数组的遍历顺序：此处采取先遍历背包，再遍历物品的方式，物品和背包都采取从前向后遍历的方式

3. 举例验证：对于 s="applepenapple" wordDict=["apple","pen"] 动态规划数组的推导过程为：验证成立

1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,1,

将问题转化为完全背包问题，那么此处背包的容量就是 n ，并没有给定相应的物品，但是要将背包 n 装满，那么使用的物品就应该是 1-n 中的全部完全平方数，首先创建物品数组。

1
2
3
4

vector<int> nums;
for(int i=1;i*i<=n;i++){
    nums.push_back(i*i);
}

那么此处的物品数组就是 nums ，在物品数组中选取物品将背包装满，要求使用的物品数量能少。那么此处的处理方式就是和322.零钱兑换完全相同。此处求解的是最少的完全平方数的个数，不存在组合和排列的问题，因此既可以先遍历背包也可以先遍历物品。

1. 动态规划数组的定义：定义数组 dp[n+1] 表示总和为 n 的最少的完全平方数的数量

2. 动态规划数组的推导：在第 i 次迭代中，考虑元素 nums[i] ，尝试使用 nums[i] 来减少数量 dp[j]=min(dp[j],dp[j-nums[i]]+1) （此处需要判断 dp[j-nums[i]]!=INT_MAX）

3. 动态规划数组的初始化：对于 dp[0] 实际是不符合问题的定义，为了满足后续的计算，将其初始化为 dp[0]=0 ，对于其他元素，由于递推方式为 dp[j]=min(dp[j],dp[j-nums[i]]+1) 那么对于初始不能恰好装满的容量，都初始化为 INT_MAX 。

4. 动态规划数组的遍历顺序：此处先遍历物品再遍历背包，并且都采用从前向后的遍历方式。

5. 举例验证：n=13

dp={0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13}
dp={0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4}
dp={0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2}

动态规划

不同于518.零钱兑换II，此处需要求解的是，使用最少的硬币个数得到整数 amount ，此处的硬币数量是无限的。此处是一个组合问题，不存在选取顺序的问题。将之转化为完全背包问题：背包的容量为 amount ，物品的重量为 coins ，每一个物品的价值都为1，此处求解的是物品的最小价值。但是，此处的不同点在与，在向背包中装入物品时，要求将背包恰好装满。

1. 动态规划数组的定义：定义动态规划数组 dp[amount+1] 表示将 amount 装满所需的最少硬币个数。

2. 动态规划数组的推导：在第 i 次迭代中，在硬币 0-i 中进行选择，那么主要是 coins[i] 的选择问题。此处在进行递推时，需要考虑到可行的条件。首先是 dp[j] 的值，若是 dp[j]=-1 说明之前不存在方案将之装满，那么就需要查看 dp[j-coins[i]] 的值是否为 -1 ，若是为说明当前依旧无法装满，不修改值，负责当前存在从 dp[j-coins[i]] 的基础上将之装满的方案，对应需要的最少硬币数就是 dp[j-coins[i]]+1 ，若是 dp[j]!=-1 ，说明当前就存在可以装满的方案，那么尝试装入 coins[i] 看能否更少，当然需要 dp[j-coins[i]]!=-1 ，那么总体的推导过程就是：

1
2
3
4
5
6
7

if(dp[j]!=-1){
    if(dp[j-coins[i]]!=-1)
        dp[j]=min(dp[j],dp[j-coins[i]]+1);
}else{
    if(dp[j-coins[i]]!=-1)
        dp[j]=dp[j-coins[i]]+1;
}

1. 动态规划数组的初始化：在初始时全部初始为 -1 表示不存在装满的方案，而对于 dp[0] 装满0的背包，只需要0个硬币，初始化为 dp[0]=0

2. 动态规划数组的遍历顺序：此处先遍历物品，再遍历背包，并且在对背包遍历时从前向后遍历。

3. 举例验证： coins = [1, 2, 5], amount = 11 那么动态规划数组的推导过程为：

>
dp={0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11}
dp={0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6}
dp={0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3}