Map of Augustus's Soul

Algo Revised: Dynamic Programing

Posted on Edited on In Valine:
Symbols count in article: 25k Reading time ≈ 1:04

Longest ZigZag Path in a Binary Tree

尾递归的构建方式 在参数当中完成运算。

本题最优解不依赖于子问题的解，因为有可能子问题中出现最大解但是对于父问题来说不符合加1的要求，例如最长Z路径出现在中间段，所以采用外部设置全局变量比较更新的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int maxlen=0;
    void tail_recusion(int len,int direct,TreeNode* root)
    {
        maxlen = max(maxlen,len);
        if(root)
        {
            if(direct==1)//上一次走的是右侧 即当前节点是父节点的右子树
            {
                if(root->left)
                    tail_recusion(len+1,0,root->left);
                if(root->right)
                    tail_recusion(1,1,root->right);
            } 
            else//当前节点是父节点的左子树
            {
                if(root->left)
                    tail_recusion(1,0,root->left);//1 是为了在下一层中记录本层的位置
                if(root->right)
                    tail_recusion(len+1,1,root->right);
            }        
        }
         
    }
    int longestZigZag(TreeNode* root) {
        tail_recusion(0,0,root);
        tail_recusion(0,1,root);
        return maxlen;
    }
};

887. Super Egg Drop

重点:描述出状态 找到状态转移方程 本题特征: 利用函数的单调性来逼近答案（这是本题规划的部分）

image-20210526153430141

image-20210526153443782

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    map<int,int> memo;//dp中用于存储的字典
    int dp(int k,int n)
    {
        if(memo.find(100*n+k)==memo.end())//找不到
        {
            int ans = 0;
            if(k==1)
                ans=n;
            else if(n==0)
                ans=0;
            else 
            {
                int low =1;
                int high=n;
                while(low+1<high)//是离散的点 所以只能用间隔逼近
                {
                    int x = low + (high-low)/2;
                    int t1 = dp(k,n-x);
                    int t2 = dp(k-1,x-1);
                    if(t1>t2)
                        low = x;
                    else if(t1<t2)
                        high=x;
                    else    
                        low = high = x;
                }
                ans=1+min(max(dp(k,n-low),dp(k-1,low-1)),max(dp(k,n-high),dp(k-1,high-1)));
            }
            memo[100*n+k]=ans;
        }   
        return memo[100*n+k];//利用一个函数映射 把二维降为一维存储
    }
    int superEggDrop(int K, int N) {
        return dp(K,N);
    }
};

20220118 树状分析改为动态规划：二分法想到的是对的 最后本质采用了二分查找；压缩的本质是 m~n可以用n-m来表示

131. Palindrome Partitioning

回溯法写对了 关键在于去除冗余计算

在判断回文串的时候有冗余 dp判断是否是回文串

如果直接采用课堂上二维矩阵的方式来记录的话，需要分配的空间过大

dp判断s[i]~s[j]是否是回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<vector<string>> ans;
    vector<vector<bool>> jdg;
    void judge(string s)
    {
        for(int i=s.size()-1;i>=0;--i)
        {
            for(int j=i+1;j<s.size();++j)
            {            
                jdg[i][j]=(s[i]==s[j])&&jdg[i+1][j-1];
            }
        }//转移方程依赖[i+1][j-1] 从末尾往前
    }
    
    
    vector<vector<string>> partition(string s) {
        int len=s.size();
        jdg.assign(len,vector<bool>(len,true));//学到新函数 注意初始化 i>=j 时都为真 边缘是i+1和j-1交错 此时依赖于i+1和j-1字符是否相等 因此应该设置为true
        judge(s);
        vector<string> set;
        backtrace(0,s,set);
        return ans;
    }
    void backtrace(int left,string s,vector<string>& set)
    {
        if(left>=s.size())
            ans.push_back(set);
        else
        {
            for(int i=left;i<s.size();++i)
            {
                if(jdg[left][i])
                {
                    set.push_back(s.substr(left,i-left+1));
                    backtrace(i+1,s,set);
                    set.pop_back();
                }
            }
        }
    }
};

时间代价：字符串长度为n，若每个字符都一样，则有2^(n-1) = O(2^n) 的分法，而每种分发都需要遍历一次字符串来获得对应的划分，加上动态规划的代价

O(n*2^n+n^2)=O(n*2^n)

空间代价 dp的数组 O(n^2)

变式 132. Palindrome Partitioning II

基于上一题的思路 就是在回溯具体切分的过程中做统计 每次到底得到答案的时候记录切分次数，在切分回溯的过程中利用已经有的答案做出剪枝

还有一个更快的思路是只统计次数 不在乎情况

不要贪心 思路是对的 先用dp求出回文的情况，计算最小分割数的时候的方程是互相依赖的且是一维的 在用上述标记做一次dp

取决于问题是从后往前分析还是从前往后；如果数组定义为从0到位置i需要的最短分割，那么是从前往后（注意！！）数组的定义会影响到问题规划的方式

方程：s[0][i]是回文的话 memo[i]=0 因为无需分割，否则对于j=[0,i], 找到一个最小的memo[j]+1 在此处使用了贪心的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    
    int minCut(string s) {
        vector<int> memo;
        vector<vector<bool>> jdg;
        memo.resize(s.size(),s.size()-1);
        jdg.assign(s.size(),vector<bool>(s.size(),true));
        for(int i=s.size()-1;i>=0;--i)
        {
            for(int j=i+1;j<s.size();++j)
                jdg[i][j]=(s[i]==s[j])&&jdg[i+1][j-1];
        }
        for(int i=0;i<s.size();++i)
        {
            if(jdg[0][i])
                memo[i]=0;
            else
            {
                for(int j=0;j<i;++j)
                    if(jdg[j+1][i])
                        memo[i]=(memo[i]>memo[j]+1)?(memo[j]+1):memo[i];
            //转移方程中 更小的值可能已经被记录 要维持最小
            }
        }
        return memo[s.size()-1];
    }
};

变式 1278. Palindrome Partitioning III

采用同样的预处理，changed[i][j]表示从s[i]到s[j]若修改为字符串需要修改的字符个数，转移方程只需要在判断的基础上略作修改即可。原本考虑用递归来表示待分割的次数k，但是这也转换为一个二维空间

为什么changed是二维而不是一维——因为同一层循环可能有不同的分割点

定义 minch[m][i] 还有m次分割机会（很重要！划重点！）下，从0号位置到i号位置最少改变的字符数

卡在的地方: 解决问题的思路（明确有二维的变量），m的取值（一开始搞成了k+1，k+1是用在不包括0的计数的情况，这里的确只有0~k），内部规划的时候 j 和 i 的关系，注意分割的时候要从下一个字符开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    int min(int a,int b)
    {
        if(a<b)
            return a;
        else
            return b;
    }
    int palindromePartition(string s, int k) {
       int len = s.size();
    vector<vector<int>> changed;
    changed.assign(len, vector<int>(len, 0));
    for (int i = len - 1; i >= 0; --i)
    {
        for (int j = i + 1; j < len; ++j)
        {
            if (s[i] == s[j])
                changed[i][j] = changed[i + 1][j - 1];
            else
                changed[i][j] = changed[i + 1][j - 1] + 1;
        }
    }//再次出现的回文处理方式

    vector<vector<int>> minch;
    minch.assign(k, vector<int>(len, INT_MAX - 2));
    for (int i = 0; i < k; ++i)
        minch[i][0] = 0;
    for (int m = 0; m < k; ++m)
    {
        //cout << "m " << m << endl;
        if (m == 0)
        {
            for (int i = 0; i < len; ++i)
            {
                minch[0][i] = changed[0][i];
            }
        }
        else
        {
            for (int i = 0; i < len; ++i)
            {
                for (int j = 0; j < i; ++j)
                {
                    //cout << minch[m - 1][j] << " " << changed[j + 1][i] << endl;
                    minch[m][i] = min(minch[m][i], minch[m - 1][j] + changed[j + 1][i]);//记住留下最小值
                }
            }
        }
        /*for (int i = 0; i < k; ++i)
        {
            for (int j = 0; j < len; ++j)
                cout << minch[i][j] << " ";
            cout << endl;
        }
        cout << endl;*/
    }
    return minch[k-1][len - 1];
    }
};

变式 5. Longest Palindromic Substring

在原本架构上增加全局变量找最大值 一开始脑子转不过来没有意识到本质是变式。可以接机复习回文串的动态规划架构

在规划顺序卡住，取决于如何分解问题：可以长度由小到大显式：

image-20210713201525528

也可以采用如下：右侧限定了左侧，右侧从小到大，左侧从最左开始填写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len<2)
            return s;
        int maxlen=0,start=0;
        vector<vector<bool>> judge(len,vector<bool>(len));
        for(int right=0;right<len;++right)
        {
            for(int left=0;left<=right;++left)
            {
                if(s[left]!=s[right])  
                {
                    judge[left][right]=false;
                    continue;
                }
                if(right-left<=2)
                    judge[left][right]=true;
                else
                    judge[left][right]=judge[left+1][right-1];
                if(judge[left][right] && right+1-left>maxlen)
                {
                    maxlen=right+1-left;
                    start=left;
                }
            }
        }
        return s.substr(start,maxlen);
    }
};

最初想到的：中心扩散法

可以优化的地方是：在剩余的长度小于maxlen/2的时候停止，因为此时不可能再有回文串比现行最大长度回文串要长；出现重复字符的时候移动指针直到下一个字符不重复，相当于根据重复字符也是回文串把重复部分压缩，然后再照常判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<2)
            return s;
        int len=s.size();
        int maxlen=0,start=0;
        for(int i=0;i<len;)
        {
            if(len-i<=maxlen/2)
                break;
            //长度为1或0必是回文 且不会再有比现行答案更长的回文串 可以早点结束
            int left=i,right=i;
            while(right<len-1 && s[right]==s[right+1])
                right++;//确认核心
            i=right+1;
            while(right<len-1 && left>0 && s[left-1]==s[right+1])
            {
                left--;
                right++;
            }
            if(maxlen<right+1-left)
            {
                maxlen=right+1-left;
                start=left;
            }
        }
        return s.substr(start,maxlen);
    }
};

变式：647. Palindromic Substrings

评论区RoundOne的dp解法很简洁 学习

139. Word Break

遇到可以匹配的词就切分并且以切分后的字串为开头继续切分 但该思路的本质是贪心策略，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len=s.size();
        vector<bool> judge(len+1,false);
        judge[0]=true;
        string str;
        int cnt=0;
        for(int i=0;i<len;++i)
        {
            str.push_back(s[i]);
            cnt++;
            if(find(wordDict.begin(),wordDict.end(),str)!=wordDict.end())
            {
                if(judge[i+1-cnt])
                {
                    cout<<"i "<<i<<" ";
                    cout<<"str "<<str<<" ";
                    cout<<"cnt "<<cnt<<" ";
                    judge[i+1]=true;
                    cnt=0;
                    str.clear();
                }
            }
            
        }
        return judge[len];
    }
};

/*
"aaaaaaa"
["aaaa","aaa"]
My output:false
Expected:true
*/

动态规划 一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len=s.size();
        vector<bool>judge(len+1,false);
        judge[0]=true;
        for(int i=0;i<len;++i)
        {
            for(int j=0;j<=i;++j)
            {
                string str = s.substr(j,i+1-j);
                if(!judge[i+1]&&find(wordDict.begin(),wordDict.end(),str)!=wordDict.end())//有可分割的情况就不再判断
                {
                    judge[i+1]=judge[j];
                }
            }
        }
        for(auto x:judge)
            cout<<x<<" ";
        return judge[len];
    }
};

10. Regular Expression Matching

关键在于意识到需要用到动态规划才能解决问题，是在测试用例

s=”aab” p=”ac*a*b”的时候意识到的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool isMatch(string s, string p) {
        auto match=[&](int i,int j)
        {
            if(i==0)//除了[0][0]之外，其他意味着空串匹配非空串
                return false;
            if(p[j-1]=='.')
                return true;
            else
                return s[i-1]==p[j-1];
        };//注意边界条件 judge[0][0]=true 是初始条件
        int m=s.size(),n=p.size();
        vector<vector<bool>> judge(m+1,vector<bool>(n+1));
        judge[0][0]=true;
        for(int i=0;i<=m;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(p[j-1]=='*')
                {
                    judge[i][j]=judge[i][j-2];//是否需要星号
                    if(match(i,j-1))
                    {
                        judge[i][j]=judge[i-1][j]||judge[i][j];
                    }
                }
                else
                {
                    if(match(i,j))
                    {
                        judge[i][j]=judge[i-1][j-1]||judge[i][j];
                    }
                }
            }
        }
        return judge[m][n];
    }
};

Letter Combinations of a Phone Number

直接做法是哈希表硬记忆，后用回溯

这里看到了一个技巧做法：统计出所有可能性（本身是连乘），然后根据计数规律来构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return {};
        vector<string> res;
        vector<string> dict={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int len=1,size=digits.size();
        for(int i=0;i<digits.size();++i)
            len=len*dict[digits[i]-'0'].size();
        for(int i=0;i<len;++i)
        {
            int last=i;
            string str;
            for(int j=size-1;j>=0;--j)
            {
                int c = digits[j]-'0';
                int pos = last%dict[c].size();
                last/=dict[c].size();//这两句决定了外层的循环是倒序并且最后需要reverse
                str.push_back(dict[c][pos]);
            }
            reverse(str.begin(),str.end());
            res.push_back(str);
        }
        return res;
    }
};

类似题：

46. Permutations

上述编号取余的方法并没有比回溯法更加高效 但是学习了unique的用法 返回一个迭代器 从begin到该迭代器 只有一个元素重复出现一次 即对于不重复出现的部分 返回的迭代器相当于end()

回溯法 注意是引用 要创建新的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
class Solution {
    List<List<Integer>> res;
    int n;
    public List<List<Integer>> permute(int[] nums) {
        this.n=nums.length;
        this.res = new LinkedList<>();
        List<Integer> output = new LinkedList<Integer>();
        for(int n : nums){
            output.add(n);
        }
        backtrace(output,0);
        return this.res;
    }
    void backtrace(List<Integer> output,int first){
        if(first==n){
            res.add(new ArrayList<Integer>(output));
            return;
        }
        for(int i=first;i<n;++i){
            Collections.swap(output,first,i);
            backtrace(output,first+1);
            Collections.swap(output,first,i);
        }
    }

}

22. Generate Parentheses

一个简单的回溯 关键是控制配对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<string> res;
    void reverse(int left,int right,char ch,string str)
    {
        if(ch=='(')
        {
            left--,right--;
            str.push_back(ch);
            if(left>0)
                reverse(left,right,'(',str);
            if(right<0)
                reverse(left,right,')',str);
        }
        else
        {
            right++;
            str.push_back(')');
            if(left>0)
                reverse(left,right,'(',str);
            if(right<0)
                reverse(left,right,')',str);
        }
        if(left==0 && right==0)
            res.push_back(str);
    }
    vector<string> generateParenthesis(int n) {
        string str = "";
        reverse(n,0,'(',str);
        return res;
    }
};

32. Longest Valid Parentheses

一开始想用栈做 但是实际情况更复杂 没有考虑括号套娃的情况

dp版：关键在于 完整的子串必定是右括号结尾，所以状态转移只需要关注右括号，左括号结尾的子串长度必定是0（全初始化为0就可以） 有两种转移状态 成对和套娃 小心下标合法性的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        int max=0;
        vector<int> dp(len,0);
        for(int i=1;i<len;++i)
        {
            if(s[i]==')')
            {
                if(s[i-1]=='(')
                    dp[i]=2+((i<2)?0:dp[i-2]);
                else
                {
                    if(i-dp[i-1]>0 && s[i-1-dp[i-1]]=='(')
                        dp[i]=2+dp[i-1]+((i-2-dp[i-1]<0)?0:dp[i-2-dp[i-1]]);
                }
            }
            max=(dp[i]>max)?dp[i]:max;
        }
        return max;
    }
};

栈：

一开始使用更多的是对符号本身是否匹配，这里改成存下标，以来通过下标的信息可以判断是否匹配，二来下标差可以直接求出子串长

这里栈底是最后一个没有被匹配的右括号的下标，之上都是可以被匹配的左括号初始化采用-1可以在开头不是右括号的情况下完成补全。

需要注意的细节：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int longestValidParentheses(string s) {
        int max=0,len=s.size();
        stack<int> stk;
        stk.push(-1);
        for(int i=0;i<len;++i)
        {
            if(s[i]=='(')
                stk.push(i);
            else
            {
                if(!stk.empty())
                {
                    stk.pop();
                    if(!stk.empty())
                        max = (i-stk.top()>max)?i-stk.top():max;
                    else
                        stk.push(i);
                }
                else
                    stk.push(i);
            }
        }
        return max;
    }
};

39. Combination Sum

卡在了具体实现上（本质就是部分和问题）

动态规划 巧用stl库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        unordered_map<int,set<vector<int>> >dict;
        for(int i=1;i<=target;++i)
        {
            for(auto it:candidates)
            {
                if(it==i)
                    dict[i].insert({it});
                else
                {
                    for(auto vec:dict[i-it])//为空会跳过
                    //没有引用符号 不会修改原来的vector
                    {
                        vec.push_back(it);
                        sort(vec.begin(),vec.end());
                        if(dict[i].count(vec)==0)//绝妙 其中的元素vector比较符号被重载了
                            dict[i].insert(vec);//没有就加入
                    }
                }
            }

        }
        vector<vector<int>> ans;
        for(auto it:dict[target])
            ans.push_back(it);
        return ans;
    }
};

回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> candi;
    void backtrace(vector<int> res,int remain)
    {
        if(remain==0)
        {
            sort(res.begin(),res.end());
            if(find(ans.begin(),ans.end(),res)==ans.end())
                ans.push_back(res);
        }
        for(auto it : candi)
        {
            if(it>remain)
                continue;
            res.push_back(it);
            backtrace(res,remain-it);
            res.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        candi = candidates;
        vector<int> res;
        backtrace(res,target);
        return ans;
    }
};

64. Minimum Path Sum

dp和记忆化搜索都可以

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[m-1][n-1]=grid[m-1][n-1];
        for(int i=m-2;i>=0;--i)
            dp[i][n-1]=grid[i][n-1]+dp[i+1][n-1];
        for(int i=n-2;i>=0;--i)
            dp[m-1][i]=grid[m-1][i]+dp[m-1][i+1];
        //初始化只能向右和只能向下的
        for(int i=m-2;i>=0;--i)
            for(int j=n-2;j>=0;--j)
                dp[i][j]=min(dp[i+1][j],dp[i][j+1])+grid[i][j];
        return dp[0][0];
    }
};

记忆化搜索另外一题：62. Unique Paths

221. Maximal Square

dp的含义：以ij为右下角的正方形的最大边长

依赖于左上方 左方 上方是否是正方形 为了统计数量方便 也可以理解为依赖于左上方 左方 上方正方形边长大小 缺一不可 所以要取三者最小值 注意边界情况（在图形边界）

可以解释为什么要考虑左侧上侧的最小值

image-20210915113432534

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int maxSide = 0;
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(columns));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;//不仅是判断 还要计数
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        maxSide * maxSide;
        return maxSquare;

    }
};

279. Perfect Squares

内层循环是在动态规划解法中是不可避免的 相信自己!

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1);
        for(int i=1;i<=n;++i){
            int minn=INT_MAX;
            for(int j=1;j*j<=i;++j)//用于找最优
                minn = min(minn,dp[i-j*j]);
            dp[i]=minn+1;
        }
        return dp[n];
    }
};

BFS 减去比自己小的完全平方数 成为树的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int numSquares(int n) {
        queue<int> que;
        set<int> visited;
        visited.emplace(n);
        que.push(n);
        int level=0;
        while(!que.empty()){
            int size = que.size();
            level++;
            for(int i=0;i<size;++i){
                int num = que.front();
                que.pop();
                for(int j=1;j*j<=num;++j){//找多种可能性
                    int residual = num-j*j;
                    if(residual==0)
                        return level;
                    else if(visited.count(residual)==0)
                    {
                        visited.emplace(residual);
                        que.push(residual);
                    }    
                }
            }
        }
        return level;
    }
};

152. Maximum Product Subarray

最长子序列的变体 关键在于从动态规划的思路理清

最大除了符号反转之外还有重新开始的可能（nums[i]自身）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int minp=nums[0],maxp=nums[0];
        int ans=nums[0];
        int tmpmax=0,tmpmin=0;
        for(int i=1;i<nums.size();++i)
        {
            tmpmax=maxp;
            tmpmin=minp;
            maxp = max(nums[i],max(tmpmax*nums[i],tmpmin*nums[i]));
            minp = min(nums[i],min(tmpmax*nums[i],tmpmin*nums[i]));
            ans=max(ans,maxp);
        }
        return ans;
    }
};

300. Longest Increasing Subsequence

和最大子串和 最大子串积是同类

动态规划 有重复遍历

贪心+二分查找——上升的尽可能慢 长度为j的最小末尾作为状态记录 遍历到一个数用二分查找来更新（可以证明最小末尾数据是递增的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=1;
        int n=nums.size();
        vector<int> d(n+1,0);
        d[len]=nums[0];
        for(int i=1;i<n;++i){
            if(nums[i]>d[len])
                d[++len]=nums[i];
            else
            {
                int l=1,r=len;
                int pos = 0;//如果都没有找到 说明所有前面的数都比当前数大
                while(l<=r){
                    int mid = (l+r)/2;
                    if(d[mid]<nums[i]){//在记录中查找
                        pos = mid;//尽量向大的靠近 因此先赋值给pos 
                        l=mid+1;
                    }
                    else    
                        r=mid-1;
                }//二分查找 目标是找到d[pos]<nums[i] && d[pos+1]>nums[i]
                d[pos+1]=nums[i];
            }
        }
        return len;
    }
};

309. Best Time to Buy and Sell Stock with Cooldown

How to come up with the idea that using dynamic programming?

multiple states+rely on state of previous day

Because it has three different decisions in one day, dp vector should be two-dimension.

To optimize the space, we notice that every step is only dependent to its previous one step. So we can use single variable instead of vector to memorize states. In this way the memory used is back to one dimension but it is a bit different to my original thought, which only consider the time series.

Another point is to figure out how the state changes with cool-down. Devide the state into three situations: stock, not stock and cool, not stocking and not cool.

For day i, Stock means you have bought stocks previous day, so state is same as day i-1 stock. Or you bought it today, which means you cannot cool down and have stocks yesterday. So it is not stock and not cool plus your cost of buying stocks.

For day i, not stock and not cool means you have no stocks yesterday ( same as day i-1 no-stocks-no-cool);or you are cool down yesterday.

For day i, not stock and cool means you sold your stocks yesterday, which is day i-1 stock plus the price you sold them.

Besides, for initialization, stock means you bought stocks on that day, so it’s minus. It’s impossible for first day to be cool-down but we still set it zero,same as no-stocks-no-cool. We can take it as sell at 0 before.

Last, it’s meaningless to have stocks at last day, so the answer comes from cool-down and no-stocks-no-cool.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int stock=-prices[0];
        int cool = 0;
        int nsnc = 0;
        for(int i=1;i<prices.size();++i){
            int newst = max(stock,nsnc-prices[i]);
            int newcool = stock+prices[i];
            int newnsnc = max(nsnc,cool);
            stock = newst;
            cool = newcool;
            nsnc = newnsnc;
        }
        return max(cool,nsnc);
    }
};

198. House Robber

小心初始化的时候 第二个位置是取前两个的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1)
            return nums[0];
        else if(n==2)
            return max(nums[0],nums[1]);
        vector<int> dp(n,0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);//attention
        for(int i=2;i<n;++i)
        {
            dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[n-1];
    }
};

可以发现 实际上只需要存前两栋房屋的最大值就可以了 再往前的不需要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int rob(vector<int>& nums) {
        int house1=0,house2=0;
        if(nums.size()<2)
            return nums[0];
        else
        {
            house1 = nums[0];
            house2 = max(nums[0],nums[1]);
        }
        int ans=house2;//不能设置为0 否则nums.size()==2时出错
        for(int i=2;i<nums.size();++i)
        {
            ans = max(house1+nums[i],house2);
            house1 = house2;
            house2=ans;
        }
        return ans;
    }
};

337. House Robber III

曾经的算法题复习 是否要取状态要记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    unordered_map<TreeNode*,int> yes;
    unordered_map<TreeNode*,int> no;
    void robPlan(TreeNode* root)
    {
        if(!root)
            return ;
        if(!root->left && !root->right)
        {
            yes[root]=root->val;
            no[root]=0;
        }
        robPlan(root->left);
        robPlan(root->right);

        yes[root]=root->val+no[root->left]+no[root->right];
        no[root]=max(yes[root->left],no[root->left])+max(yes[root->right],no[root->right]);
    }
    int rob(TreeNode* root) {
        robPlan(root);
        return max(yes[root],no[root]);
    }
};

312. *Burst Balloons

memorized search

if deleting ballon, two non-adjacent balloons will become adjacent. So we can take deletion as addition(Last one deleted). And use addtion to partition. Try every possible solution to find out currently max count.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> val;
    vector<vector<int>> rec;
    int solve(int left,int right)
    {
        if(left>=right-1)//open interval 
            return 0;
        if(rec[left][right]!=-1)
            return rec[left][right];
        else
        {
            for(int mid=left+1;mid<right;++mid)
            {
                int sum=val[left]*val[right]*val[mid];
                sum+=solve(left,mid)+solve(mid,right);
                rec[left][right]=max(rec[left][right],sum);
            }
        }
        return rec[left][right];
    }
    int maxCoins(vector<int>& nums) {//take deletion as addition
        int n=nums.size();
        val.resize(n+2);
        for(int i=1;i<=n;++i)
            val[i]=nums[i-1];
        val[0]=1;
        val[n+1]=1;
        rec.resize(n+2,vector<int>(n+2,-1));//-1 means not calculated
        return solve(0,n+1);
    }
};

Change the sequence to calculate. So we have dynamic programming.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        vector<int> val(n+2);
        for(int i=1;i<=n;++i)
            val[i]=nums[i-1];
        val[0]=1;
        val[n+1]=1;
        vector<vector<int>> rec(n+2,vector<int>(n+2,0));
        for(int i=n-1;i>=0;--i)//left
        {
            for(int j=i+2;j<=n+1;++j)//right
            {
                for(int k=i+1;k<j;++k)//mid
                {
                    int sum=val[i]*val[k]*val[j];
                    sum+=rec[i][k]+rec[k][j];
                    rec[i][j]=max(sum,rec[i][j]);
                }
            }
        }
        return rec[0][n+1];
    }
};

416. Partition Equal Subset Sum

一个背包问题 转换为所有值的一半 应该复习的问题 算法课出现过

背包问题用一维是解决不了的 因为需要记录目前加了什么值

dp[i][j]的含义 对目标j数组里的前i个数是否能满足

由于只求一半 所以j的范围在0~target就可以 即数组建立为target+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        if(n<2)
            return false;
        int sum=accumulate(nums.begin(),nums.end(),0);
        int maxNum=*max_element(nums.begin(),nums.end());
        if(sum & 1)
            return false;//是奇数
        int target = sum/2;
        if(maxNum>target)
            return false;//最大数比一半还大 不可能
        vector<vector<int>> dp(n,vector<int>(target+1，0));//不写0剩下也默认是false
        for(int i=0;i<n;++i)
            dp[i][0]=true;//initialise 小心转移方程和初始化
        dp[0][nums[0]]=true;//0~0 谁都可以 这是起点 需要为真 ！！！！
        for(int i=1;i<n;++i)
        {
            int num=nums[i];
            for(int j=1;j<=target;++j)//从左到右填表
            {
                if(j>=num)
                    dp[i][j]=dp[i-1][j]|dp[i-1][j-num];
                //可以不选这个数 或者选了转译成另一个数
                else
                    dp[i][j]=dp[i-1][j];
                //不能选 只能看上一个
            }
        }
        return dp[n-1][target];
    }
};

494. Target Sum

一开始想到的逐个和累加没有排除负数

列的大小只与目标有关 转换目标

用公式转换 凑需要是负数的和

dp[i][j]的含义是前i个数凑出来负数和是j的方法数

neg没有也是一种情况

想明白传一方程:是累加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum= accumulate(nums.begin(),nums.end(),0);
        if(sum<target)
            return 0;
        if((sum-target)%2!=0)
            return 0;
        //排除一些不可能情况
        int neg = (sum-target)/2;//(sum-neg)-neg==target
        int n=nums.size();
        vector<vector<int>> dp(n+1,vector<int>(neg+1));
        for(int i=0;i<=n;++i)//0：不需要数字 
            dp[i][0]=1;
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<=neg;++j)//0 和倒扣到0 注意初始化的方向 要包括0 eg [1,0] 1
            {
                dp[i][j]=dp[i-1][j];
                if(j-nums[i-1]>=0)
                    dp[i][j]+=dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][neg];
    }
};

空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum<target)
            return 0;
        int delta = sum-target;
        if(delta%2==1)
            return 0;
        int neg = delta/2;
        //优化 只与上一行有关
        vector<int> dp(neg+1);
        dp[0]=1;
        for(auto n:nums)
        {
            for(int j=neg;j>=n;--j)//从后往前 因为依赖前面的数据 不能覆盖 同时注意下标
                dp[j]+=dp[j-n];
        }
        return dp[neg];
    }
};

322. Coin Change

When using dynamic programing, vector can be initialized to be amount+1. Such impossible value can avoid INT_MAX overflow when calculating.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+2);
        dp[0]=0;//因为不限次数 所以dp[i]代表amount=i时的方法
        for(int i=1;i<=amount;++i)
        {
            for(auto n:coins)
            {
                if(i-n>=0)
                    dp[i]=min(dp[i],dp[i-n]+1);
            }
        }
        return dp[amount]==amount+2?-1:dp[amount];
    }

剑指 Offer 10- I. 斐波那契数列

注意返回的答案应当是f_n_1（Fn-1）；以及按照题目要求每个答案都要取模

1048. Longest String Chain

一开始想到用回溯 但是在边界情况一直出错 可以用动态规划 避免一开始的是否需要加入的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    boolean judge(String shorter,String longer){
        if(shorter.length()+1 != longer.length())
            return false;
        int insert=1;
        int i=0,j=0;
        while(i<shorter.length() && j < longer.length()){
            if(shorter.charAt(i)!=longer.charAt(j))
                insert--;
            else{
                ++i;//匹配了 前身的指针才移动 否则让插入 后者的指针一直移动
            }
            if(insert<0)
                return false;
            ++j;
        }
        return true;
    }
    public int longestStrChain(String[] words) {
        int ans = 0;
        List<String> wordsList =Arrays.asList(words);
        wordsList.sort(new Comparator<String>(){
            @Override
            public int compare(String s1,String s2){
                return s1.length()-s2.length();
            }
        });
        for(String str:wordsList){
            System.out.printf("%s ",str);
        }
        System.out.println("");
        int n = wordsList.size();
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=0;i<n;++i){
            for(int j=0;j<i;++j){
                if(judge(wordsList.get(j),wordsList.get(i))){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            ans = Math.max(dp[i],ans);
        }
        for(int i=0;i<n;++i)
            System.out.printf("%d ",dp[i]);
        return ans;
    }
}

375. Guess Number Higher or Lower II 220127x

最开始想到了树，在这过程中想到了区间分治可以用记忆话搜索或者动态规划

预打表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    static int N = 200;
    static int[][] cache = new int[N+10][N+10];
    //下标会到n
    //打表预处理
    static{
        for(int len=2;len<=N;++len){
            for(int l=1;l+len-1<=N;++l){
                //有减一的操作
                int r = l+len-1;
                cache[l][r]=0x3f3f3f3f;
                for(int i=l;i<=r;++i){
                    int cur = Math.max(cache[l][i-1],cache[i+1][r])+i;
                    cache[l][r]=Math.min(cache[l][r],cur);
                }
            }
        }
    }
    public int getMoneyAmount(int n) {
        return cache[1][n];
    }
}