Leetcode 动态规划

139. 单词拆分 - 力扣（LeetCode）

322. 零钱兑换 - 力扣（LeetCode）

搜了一下，发现我之前居然记录过零钱兑换，俩年后又有点生疏了，不过这次至少写出来了。

一开始想的是DFS，不过一开始思路有问题，以为优先使用大额硬币就一定是最优解，但是这题不能用贪心算法，比如要凑10块钱，可用硬币是1块，5块，6块，那么优先用大额硬币是6+4×1，不如2×5。

所以用BFS搭配DP剪枝，自己写的代码有点臃肿

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0)
            return 0;
        vector<int> dp(amount+1,0);
        queue<int> now_arrived;
        int nums = 1;
        for(auto coin:coins){
            if(coin == amount)
                return nums;
            if(coin<amount){
                now_arrived.push(coin);
                dp[coin] = 1;                   
            }       
        }
        while(now_arrived.size()>0){
            nums++;
            int arrived_num = now_arrived.size();
            for(int i = 0;i<arrived_num;i++){
                int temp = now_arrived.front();
                now_arrived.pop();
                for(auto coin:coins){
                    if(temp>amount-coin)
                        continue;
                    int temp_sum = temp + coin;
                    if(temp_sum == amount)
                        return nums;
                    if(temp_sum<amount&&dp[temp_sum]==0){
                        dp[temp_sum] = nums;
                        now_arrived.push(temp_sum);
                    }
                }
            }
        }
        return -1;
    }
};

另一种思路是反过来自下而上的方式进行思考。详见题解322. 零钱兑换 - 力扣（LeetCode）

第二题是单词拆分，跌跌撞撞也是用DFS写出来了

class Solution {
public:
    //计算每个单词在字符串中对应的起始位置
    void begin_end(string s,string word,unordered_map<int,vector<int>>& word_begin_end){
        for(int i=0;i+word.size()<s.size()+1;i++){
            int j = 0;
            for(;j<word.size();j++)
                if(s[i+j] != word[j])
                    break;
            if(j == word.size()){
                if(word_begin_end.count(i)==0)
                    word_begin_end.insert({i,{i+j}});
                else
                    word_begin_end[i].emplace_back(i+j);
            }
        }
    }
    //递归搜索
    bool search(unordered_map<int,vector<int>>& word_begin_end,const int& s_size,int index,vector<int>& has_arrived){
        if(index == s_size)
            return true;
        if(has_arrived[index] == 1)
            return false;
        if(word_begin_end.count(index)==0)
            return false;
        for(auto end:word_begin_end[index]){
            if(search(word_begin_end,s_size,end,has_arrived))
                return true;
        }
        has_arrived[index] = 1;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<int,vector<int>> word_begin_end;
        vector<int> has_arrived(s.size(),0);
        for(auto word:wordDict){
            begin_end(s,word,word_begin_end);
        }
        return search(word_begin_end,s.size(),0,has_arrived);
    }
};

这题DFS，BFS，DP都可以解，详见139. 单词拆分 - 力扣（LeetCode）