顿搜
飞过闲红千叶，夕岸在哪
类目归类
动态规划——算法设计 · 篇十三
08/22
一、字符串解码
GitHub地址：字符串解码.cpp
方法
1、假设定义一个数组，dp[i]为到第i个字符所能够组成的所有编码方式的个数。
2、那么对于dp[i+1]来说，肯定至少和dp[i]一样多
3、如果第i个字符和i+1个字符可以合成一个字符，那么dp[i+1] += dp[i-1].
二、路径数目 & 最小路径和
GitHub地址：路径数目 & 最小路径和.cpp
方法
1、对于某一点dpi的路径数目，是该点正上方和正左方路径数目之和
2、dpi = dpi + dpi-1; 但是对于特殊地方需要特殊考虑
三、最大子数组乘积
GitHub地址：最大子数组乘积.cpp
最大子串乘积，由于可能出现负数。也是DP问题，也是局部最优和全局最优问题。
1、这里需要记录最小值，假设有两个数组，分别记录包括当前元素在内的子串所能构成的最大和最小值
2、然后根据这个再更新全局最大
3、至于当前最大，可能是之前最大乘以当前元素，也可能是前一个元素最小乘以当前元素，也可能是当前元素
四、编辑距离
GitHub地址：编辑距离.cpp
方法
1、使用变量dpi记录包括word1[i]在内的字符串和word2[j]在内的字符串的编辑距离
2、如果word1[i+1] == word2[j+1]， 则dpi+1 = dpi，
3、否则dpi+1 = dpi+1,不过也有可能dpi+1 = dpi+1+1或者dpi+1 ，取三者最小
五、盛水最大化
GitHub地址：盛水最大化.cpp
法一：夹逼方法
1、从数组的两段走起，每次迭代时判断左边点和右边点指向的数字哪个大
2、如果左边点小，就意味着左移动右边点不可能使得结果变得更好
3、因为瓶颈在左边点，移动右边点只会变小，所以这个时候我们选择左边点右移
4、反之，选择右边点左移，在这个过程中一直维护最大的容积
法二：
1、可以在这个序列中找到最高的柱子位置，那么从两头开始找可以盛水的多少
2、假如从头开始遍历，需要遍历到柱子最高的位置
3、遍历到当前位置，如果发现当前的柱子比之前记录的柱子高，那么更新
4、如果没有之前记录的柱子高，那么就可以计算当前柱子相对之前的高柱子的盛水量
六、股票利润最大化
GitHub地址：股票利润最大化.cpp
方法
1、这里维护两个变量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（globali）
2、另一个是当前到达第i天，最多可以进行j次交易，并且最后一次交易在当天卖，出那么最好的利润是多少（locali）
3、递推公式：globali = max(locali,glboali-1),也就是取当前局部最好和过往全局最好的其中之一
4、对于局部最好，locali = max(globali-1+maxdiff(diff,0),locali-1+diff);
