LC 509. 斐波那契数：https://leetcode.cn/problems/fibonacci-number/
class Solution {
public:
int fib(int n) {
if (n <= 1) return n;
int sum = 0,dp[2];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; ++ i){
sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return sum;
}
};LC 70. 爬楼梯：https://leetcode.cn/problems/climbing-stairs/
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
else if (n == 2) return 2;
int dp[2],sum;
dp[0] = 1;
dp[1] = 2;
for (int i = 3; i <= n; ++ i){
sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return sum;
}
};LC 746. 使用最小花费爬楼梯：https://leetcode.cn/problems/min-cost-climbing-stairs/
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int len = cost.size();
if (len == 2) return min(cost[0],cost[1]);
int dp[2],t;
memset(dp,0,sizeof(int)*2);
for (int i = 2; i <= len; ++ i){
t = min(dp[1] + cost[i - 1], dp[0] + cost[i - 2]);
dp[0] = dp[1];
dp[1] = t;
}
return dp[1];
}
};LC 62. 不同路径：https://leetcode.cn/problems/unique-paths/
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[100][100];
for (int i = 0; i < m; ++ i)
dp[i][0] = 1;
for (int i = 0; i < n; ++ i)
dp[0][i] = 1;
for (int row = 1; row < m; ++row)
for (int col = 1; col < n; ++col)
dp[row][col] = dp[row - 1][col] + dp[row][col- 1];
return dp[m - 1][n - 1];
}
};LC 63. 不同路径 II：https://leetcode.cn/problems/unique-paths-ii/
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size(), col = obstacleGrid[0].size();
if (obstacleGrid[row - 1][col - 1] == 1 || obstacleGrid[0][0] == 1) return 0;
vector<vector<int>> dp(row,vector<int>(col,0));
for (int i = 0; i < row && obstacleGrid[i][0] == 0; ++ i) dp[i][0] = 1;
for (int i = 0; i < col && obstacleGrid[0][i] == 0; ++ i) dp[0][i] = 1;
for (int i = 1; i < row; ++ i){
for (int j = 1; j < col; ++ j){
if (obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[row - 1][col - 1];
}
};LC 416. 分割等和子集：https://leetcode.cn/problems/partition-equal-subset-sum/
class Solution {
public:
bool canPartition(vector<int>& nums) {
int target = accumulate(nums.begin(),nums.end(),0);
if (target & 1) return false;
target /= 2;
int dp[10001], len = nums.size();
if (len == 1) return false;
memset(dp,0,sizeof(int)*10001);
for (int i = 0; i < len; ++ i)
for (int j = target; j >= nums[i]; --j)
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
return (dp[target] == target);
}
};LC 1049. 最后一块石头的重量 II：https://leetcode.cn/problems/last-stone-weight-ii/
1049. 最后一块石头的重量 II - 力扣（LeetCode）
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int len = stones.size();
if (len == 1) return stones[0];
int dp[15001], sum = accumulate(stones.begin(),stones.end(),0),target = sum/2;
memset(dp,0,sizeof(int)*15001);
for (int i = 0; i < len; ++ i)
for (int j = target; j >= stones[i]; --j)
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
return sum - dp[target] - dp[target];
}
};LC 494. 目标和：https://leetcode.cn/problems/target-sum/
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(),nums.end(),0);
if (abs(target) > sum) return 0;
if ((target + sum) % 2 == 1) return 0;
int bagSize = (target + sum)/2;
vector<int> dp(bagSize + 1,0);
dp[0] = 1;
for (int i = 0; i < nums.size(); ++i)
for (int j = bagSize; j >= nums[i]; --j)
dp[j] += dp[j - nums[i]];
return dp[bagSize];
}
};LC 474. 一和零：https://leetcode.cn/problems/ones-and-zeroes/
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));
for (const string& str : strs){
int zeroNum = 0, oneNum = 0;
for (const char& v : str){
if (v == '1') ++oneNum;
else ++zeroNum;
}
for (int i = m; i >= zeroNum; -- i)
for (int j = n; j >= oneNum; -- j)
dp[i][j] = max(dp[i][j],dp[i - zeroNum][j - oneNum] + 1);
}
return dp[m][n];
}
};LC 518. 零钱兑换 II：https://leetcode.cn/problems/coin-change-ii/
class Solution {
public:
int change(int amount, vector<int>& coins) {
int dp[5001];
memset(dp,0,sizeof(int)*5001);
dp[0] = 1;
for (int i = 0; i < coins.size(); ++ i)
for (int j = coins[i]; j <= amount; j++)
dp[j] += dp[j - coins[i]];
return dp[amount];
}
};LC 377. 组合总和 Ⅳ：https://leetcode.cn/problems/combination-sum-iv/
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int dp[1001];
memset(dp,0,sizeof(int)*1001);
dp[0] = 1;
for (int i = 0; i <= target; ++ i)
for (int j = 0; j < nums.size(); ++ j)
if (i - nums[j] >= 0 && dp[i] < INT_MAX-dp[i - nums[j]])
dp[i] += dp[i - nums[j]];
return dp[target];
}
};LC 322. 零钱兑换：https://leetcode.cn/problems/coin-change/
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1,INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; ++ i)
for (int j = 0; j < coins.size(); ++ j)
if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX)
dp[i] = min(dp[i],dp[i - coins[j]] + 1);
if (dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};LC 279. 完全平方数：https://leetcode.cn/problems/perfect-squares/
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1,INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; ++ i)
for (int j = 1; j * j <= i; ++ j )
dp[i] = min(dp[i],dp[i - j*j] + 1);
return dp[n];
}
};LC 139. 单词拆分：https://leetcode.cn/problems/word-break/
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+1,false);
unordered_set<string> wordMap(wordDict.begin(),wordDict.end());
dp[0] = true;
for(int i = 1; i <= s.size(); ++ i){
for (int j = 0; j < i; ++ j){
string str = s.substr(j,i - j);
if (wordMap.find(str) != wordMap.end() && dp[j]) dp[i] = true;
}
}
return dp[s.size()];
}
};LC 198. 打家劫舍：https://leetcode.cn/problems/house-robber/
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (!len) return 0;
if (len == 1) return nums[0];
int dp[101];
memset(dp,0,sizeof(int)*101);
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for (int i = 2; i < len; ++ i)
dp[i] = max(dp[i - 2] + nums[i],dp[i -1]);
return dp[len - 1];
}
};LC 213. 打家劫舍 II：https://leetcode.cn/problems/house-robber-ii/
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 1) return nums[0];
else if (len == 2) return max(nums[0],nums[1]);
else if (!len) return 0;
auto robHelper = [&](const vector<int>& nums,
const int& start,const int& end)
{
// 初始化条件和递推条件和打家劫舍I 一样
// https://leetcode.cn/problems/house-robber/description/
vector<int> dp(len);
dp[start] = nums[start];
dp[start + 1] = max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; ++ i)
dp[i] = max(dp[i - 1],dp[i - 2] + nums[i]);
return dp[end];
};
return max(robHelper(nums, 0, len - 2),
robHelper(nums, 1, len - 1));
}
};LC 337. 打家劫舍 III：https://leetcode.cn/problems/house-robber-iii/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 递归
// if (root == nullptr) return 0;
// int money = root->val;
// if (root->left)
// money += rob(root->left->left) + rob(root->left->right);
// if (root->right)
// money += rob(root->right->left) + rob(root->right->right);
// return max(money,rob(root->left) + rob(root->right));
unordered_map<TreeNode*,int> f,g;
void dfs(TreeNode* node)
{
if (!node) return;
dfs(node->left);
dfs(node->right);
f[node] = node->val + g[node->left] + g[node->right];
g[node] = max(f[node->left], g[node->left]) + max(f[node->right],g[node->right]);
}
int rob(TreeNode* root) {
dfs(root);
return max(f[root],g[root]);
}
};LC 121. 买卖股票的最佳时机：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
class Solution {
public:
// greedy - LC 121 ：这只股票只能交易一次。
// 所以可以边扫描边求出前某天到当天的买卖利润，求这些交易对的最大值即是最大利润。
// -- 这个算法成立的前提是这只股篇只能交易一次。LC121 题目描述不讲人话。
// 测试用例 [7,1,6,3,6,4] - 输出: 5
int maxProfit(vector<int>& prices) {
int Purchase = INT_MAX, Profit = 0;
for (int i : prices)
{
Purchase = std::min(i,Purchase);
Profit = std::max(Profit,i - Purchase);
}
return Profit;
}
};LC 122. 买卖股票的最佳时机 II：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
greed
class Solution {
public:
// greedy
int maxProfit(vector<int>& prices) {
int Purchase = prices[0], Profit = 0, i = 1, size = prices.size();
for(;i < size; ++ i)
{
if (prices[i - 1] < prices[i])
{
Purchase = prices[i - 1];
Profit += (prices[i] - prices[i - 1]);
}
}
return Profit;
}
};dp
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxTotal = 0;
for(int i = 0; i < prices.size() - 1; ++ i){
maxTotal += max(prices[i + 1] - prices[i],0);
}
return maxTotal;
}
};LC 123. 买卖股票的最佳时机 III：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& prices) {
int k = 2;
int len = prices.size();
if (len == 0) return 0;
vector<vector<int>> dp(len,vector<int>(2*k + 1,0));
// init
for (int i = 1; i < 2*k; i += 2)
dp[0][i] = -prices[0];
for (int i = 1; i < len; ++ i)
{
for (int j = 0; j < 2*k - 1; j += 2)
{
// buy
dp[i][j + 1] = std::max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
// sell
dp[i][j + 2] = std::max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[len-1][2*k];
}
};LC 188. 买卖股票的最佳时机 IV：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int len = prices.size();
if (len == 0) return 0;
vector<vector<int>> dp(len,vector<int>(2*k + 1,0));
// init
for (int i = 1; i < 2*k; i += 2)
dp[0][i] = -prices[0];
for (int i = 1; i < len; ++ i)
{
for (int j = 0; j < 2*k - 1; j += 2)
{
// buy
dp[i][j + 1] = std::max(dp[i - 1][j + 1] /* hold on */, dp[i - 1][j] - prices[i]/* buy */);
// sell
dp[i][j + 2] = std::max(dp[i - 1][j + 2] /*hold on */, dp[i - 1][j + 1] + prices[i] /* sell */);
}
}
return dp[len-1][2*k];
}
};LC 309. 最佳买卖股票时机含冷冻期：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& prices) {
// prof0[profit]: 手上持有股票的最大收益 -- max(prof0,prof2 - prices[i])
// prof1: 手上不持有股票，并且处于冷冻期中的累计最大收益 prof0 + prices[i]
// prof2: 手上不持有股票，并且不在冷冻期中的累计最大收益 max(prof1,prof2)
// ans = max(f1,f2)
int len = prices.size();
if (len == 0 || len == 1) return 0;
int prof0 = -prices[0], prof1 = 0, prof2 = 0,i = 1;
for (;i < len; ++ i)
std::tie(prof0,prof1,prof2) = std::make_tuple(max(prof0,prof2 - prices[i]),
prof0 + prices[i], max(prof1,prof2));
return max(prof1,prof2);
}
};LC 714. 买卖股票的最佳时机含手续费：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int len = prices.size(), i = 1, profit = 0, purchase = prices[0] + fee;
for (; i < len; ++ i)
{
// 买
if (prices[i] + fee < purchase)
{
purchase = prices[i] + fee;
}
// 卖
else if (prices[i] > purchase)
{
profit += (prices[i] - purchase);
purchase = prices[i];
}
}
return profit;
}
};LC 300. 最长递增子序列：https://leetcode.cn/problems/longest-increasing-subsequence/
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int MaxCnt = 1, len = nums.size();
if (len == 1) return 1;
// 初始化 ： 将元素分割单元素独立序列，此时每个元素的对应dp 记录是1 因为一个数也能构成递增子序列，其最大长度是1
vector<int> dp(len,1);
// 双指针 i : 右边界
for (int i = 0; i < len; ++ i)
{
// 双指针 j : 左边界 逐渐往 右边界移动 -> i
for (int j = 0; j < i; ++ j)
{
// 存在顺序对 -- 逆序对的对应说法
if (nums[j] < nums[i])
{
// 表是从左向右填的...
// 当前记录（有边界记录值） = 当前记录，左边界+1; 取最大
dp[i] = max(dp[i],dp[j] + 1);
MaxCnt < dp[i] ? MaxCnt = dp[i] : MaxCnt;
}
}
}
return MaxCnt;
}
};LC 674. 最长连续递增序列：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
class Solution {
public:
// [1,3,5,4,2,3,4,5]
int findLengthOfLCIS(vector<int>& nums) {
// 初始化 ： 不管多少个元素，只要有元素那么就会存在 就可以分割为单元素的连续递增子序列 ：
// 一个元素也是连续递增子序列
int MaxCnt = 1, cnt = 1, len = nums.size();
if (len == 1) return cnt;
for (int i = 0; i < len - 1; ++ i)
{
if (nums[i] < nums[i + 1])
{
++ cnt;
MaxCnt < cnt ? MaxCnt = cnt : MaxCnt;
}
else
cnt = 1;
}
return MaxCnt;
}
};LC 718. 最长重复子数组：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size(), ans = 0;
if (!n || !m) return 0;
vector<vector<int>> dp(n + 1,vector<int>(m + 1,0));
for (int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= m; ++ j)
{
if (nums1[i - 1] == nums2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
ans = max(ans,dp[i][j]);
}
}
return ans;
}
};LC 1143. 最长公共子序列：https://leetcode.cn/problems/longest-common-subsequence/
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size(), m = text2.size();
char c1,c2;
if (!n || !m) return 0;
vector<vector<int>> dp(n + 1,vector<int>(m + 1,0));
for (int i = 1; i <= n; ++ i)
{
c1 = text1.at(i - 1);
for(int j = 1; j <= m; ++ j)
{
c2 = text2.at(j - 1);
if (c1 == c2)
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
};LC 1035. 不相交的线：https://leetcode.cn/problems/uncrossed-lines/
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size(), num1, num2;
vector<vector<int>> dp(n + 1,vector<int>(m + 1,0));
for (int i = 1; i <= n; ++i)
{
num1 = nums1[i - 1];
for (int j = 1; j <= m; ++ j)
{
num2 = nums2[j - 1];
dp[i][j] = num1 == num2 ? dp[i - 1][j - 1] + 1 : max(dp[i][j - 1],dp[i - 1][j]);
}
}
return dp[n][m];
}
};LC 53. 最大子数组和：https://leetcode.cn/problems/maximum-subarray/
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
int sum = 0,maxSumSeq = INT32_MIN;
for (int i = 0; i < nums.size(); ++ i){
sum += nums[i];
if (maxSumSeq < sum) maxSumSeq = sum;
if (sum <= 0) sum = 0;
}
return maxSumSeq;
}
};LC 392. 判断子序列：https://leetcode.cn/problems/is-subsequence/
class Solution {
public:
bool isSubsequence(string s, string t) {
if (!s.length()) return true;
int i = 0;
for (char c : t)
if (s[i] == c && ++i == s.length()) return true;
return false;
}
};LC 115. 不同的子序列：https://leetcode.cn/problems/distinct-subsequences/
class Solution {
public:
int numDistinct(string s, string t) {
int sLen = s.length(), tLen = t.length();
if (sLen == tLen && s == t) return 1;
vector<vector<int>> dp(sLen + 1,vector<int>(tLen + 1));
// solution for rang i,j dp[i][j] ->
// case a: i == 0 dp[0][j] = 0;
// case b: j == 0 dp[i][0] = 1;
// case c: s[i - 1] != t[j - 1] dp[i][j] = dp[i - 1][j]
// case d: s[i - 1] == t[j - 1] dp[i][j] = dp[i-1][j-1] + dp[i - 1][j]
for (int i = 0; i < sLen + 1; ++ i)
{
for (int j = 0; j < tLen + 1; ++ j)
{
if (j == 0) dp[i][j] = 1;
else if (i == 0) dp[i][j] = 0;
else
{
if (s[i - 1] == t[j - 1])
dp[i][j] = (0LL + dp[i - 1][j - 1] + dp[i - 1][j]) % INT_MAX /* 此处有溢出测试用例 */;
else
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[sLen][tLen];
}
};LC 583. 两个字符串的删除操作：https://leetcode.cn/problems/delete-operation-for-two-strings/
583. 两个字符串的删除操作 - 力扣（LeetCode）
class Solution {
public:
int minDistance(string word1, string word2) {
// 此问题可转化为最长公共字序列（序列长度len(substr），
// 然后 len(word1) + len(word2) - len(substr)*2 即为题解
// LC1143 longestCommonSubsequence https://leetcode.cn/problems/longest-common-subsequence/
// longestCommonSubsequence Solution:
// case a: word1[i - 1] == word2[j - 1] dp[i][j] = dp[i - 1][j - 1] + 1
// case b: word1[i - 1] != word2[j - 1] dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
if (word1 == word2) return 0;
int wLen1 = word1.length(), wLen2 = word2.length();
vector<vector<int>> dp(wLen1 + 1,vector<int>(wLen2 + 1,0));
for (int i = 1; i <= wLen1; ++ i)
{
for (int j = 1; j <= wLen2; ++ j)
{
if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
}
}
return wLen1 + wLen2 - dp[wLen1][wLen2]*2;
}
};LC 72. 编辑距离：https://leetcode.cn/problems/edit-distance/
class Solution {
public:
int minDistance(string word1, string word2) {
if (word1 == word2) return 0;
int wlen1 = word1.length(), wlen2 = word2.length();
vector<vector<int>> dp(wlen1 + 1,vector<int>(wlen2 + 1,0));
// solution:
// case a: world1[i - 1] == world1[j - 1] = dp[i - 1][j - 1]
// case b: world1[i - 1] != world1[j - 1] = min(dp[i - 1][j - 1],dp[i][j - 1]);
for (int i = 0; i <= wlen1; ++ i) dp[i][0] = i;
for (int i = 0; i <= wlen2; ++ i) dp[0][i] = i;
for (int i = 1; i <= wlen1; ++ i)
{
for (int j = 1; j <= wlen2; ++ j)
{
if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min({dp[i][j - 1],dp[i - 1][j], dp[i - 1][j - 1]}) + 1;
}
}
return dp[wlen1][wlen2];
}
};LC 647. 回文子串 (统计回文子串数)：https://leetcode.cn/problems/palindromic-substrings/
class Solution {
public:
int countSubstrings(string s) {
if (s.size() == 1) return 1;
vector<vector<bool>>dp(s.size() + 1,vector<bool>(s.size() + 1,false));
int len = s.size(), row = len - 1, cnt = 0;
// 注意这个二维表的填法：是倒过来，从右下角往上填的上半三角形
// row 二维表行，col 二维表列
for(;row >= 0; -- row)
{
for (int col = row; col < len; ++ col)
{
if (s[row] == s[col] && (col - row <= 1 || dp[row + 1][col - 1]))
{
dp[row][col] = true;
++ cnt;
}
}
}
return cnt;
}
};LC 516. 最长回文子序列：https://leetcode.cn/problems/longest-palindromic-subsequence/
class Solution {
public:
int longestPalindromeSubseq(string s) {
int len = s.size();
// if (len == 1) return 1;
vector<vector<int>> dp(len,vector<int>(len,0));
for(int i = 0; i < len; ++ i) dp[i][i] = 1;
for (int i = len - 1; i >= 0; -- i)
{
for (int j = i + 1; j < len; ++ j)
{
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][len - 1];
}
};