力扣刷题记录10.10

今天主要复习动态规划

二、2024/10/10

（1）一维动态规划

爬楼梯和打家劫舍秒了😘（再不秒也别学了）

1、单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set <string> wordSet;
        for(string str: wordDict){
            wordSet.insert(str);
        }
        auto dp=vector<int> (s.size()+1);
        dp[0]=true;
        for(int i=1;i<=s.size();i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&wordSet.find(s.substr(j,i-j))!=wordSet.end())
                  {
                    dp[i]=true;
                    break;
                  }  
            }
        }
        return dp[s.size()];
    }
};

这道题的思路有点超纲吧！！！！！

这个动态规划的意思是，首先外循环是到单词的第i个字符，然后想要判断前i个字符能否通过字典中的单词拼出。内循环就是让j从0开始，一直到第i个字符，如果前j个字符能通过字典拼出来，而且第j到i个字符组成的字符串也能在字典中找到，那么就说明前i个字符能通过字典拼出。于是依此类推。

重点：

• 初始化动态规划数组的时候，0代表前零个字符，1才是代表一个字符。dp[0]是一定要初始化为true的，这点很关键。
• 使用unordered_set是为了使得搜索更快，降低时间复杂度。

2、杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

首先欣赏一下官方的解法：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

• 初始化结果容器：定义二维数组，numRows行，我们会逐行填充。
• 遍历：设置每一行的大小并填充边界元素；根据上一行填充中间元素

再看看我的狗屎一样的解法。。。。。为什么官方的这么优美

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        vector<int> pre(1,1);
        ans.push_back(pre);
        if(numRows==1){
            return ans;
        }
        pre={1,1};
        ans.push_back(pre);
        if(numRows==2)
            return ans;
        for(int i=3;i<=numRows;i++){
            vector <int> cur(i);
            for(int j=0;j<i;j++){
                cur[j]=(j-1>=0?pre[j-1]:0)+(j<i-1?pre[j]:0);
            }
            pre=cur;
            ans.push_back(cur);
        }
        return ans;
    }
};

3、完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                minn = min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
};

首先初始化动态规划数组，依旧是遍历0->n；初始化时f[0]=0；

f[i]表示可以将整数i表示为平方数的最小数量

内层循环，枚举所有小于等于i的完全平方数，并找到所有可能的f[i-j*j]的最小值。f[i-j*j]表示i减去一个完全平方数后剩余部分所需要的最少数量，并维护最小值。

f[i]=minn+1，因为减掉了j*j。

4、零钱兑换

为什么这道题做了无数遍还记不住。。

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

int coinChange(vector<int>& coins, int amount) {
    int Max = amount + 1;  // 设定一个大于 amount 的初始值，用来表示无法凑出的情况
    vector<int> dp(amount + 1, Max);  // 初始化 dp 数组，大小为 amount+1，值为 Max
    dp[0] = 0;  // 初始条件：凑成 0 金额需要 0 个硬币
    for (int i = 1; i <= amount; ++i) {  // 遍历每个金额 i
        for (int j = 0; j < (int)coins.size(); ++j) {  // 遍历每个硬币面值
            if (coins[j] <= i) {  // 如果硬币面值小于等于当前金额
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);  // 状态转移：使用该硬币的情况
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];  // 如果 dp[amount] 超过 amount，说明无法凑出，返回 -1
}

动态规划的核心是通过子问题的最优解构造出整个问题的最优解。在这个问题中，我们可以设定一个状态 dp[i]，表示凑成金额 i 需要的最少硬币数。

1、状态定义

• dp[i] 表示凑成金额 i 所需的最少硬币数。
• 目标是求解 dp[amount]。

2、转移方程

• 对于每个金额 i，我们可以通过使用一个面值为 coins[j] 的硬币，来从金额 i - coins[j] 转移到 i。
• 也就是说，如果要凑出金额 i，我们可以从 i - coins[j] 的金额开始，再加上一个面值为 coins[j] 的硬币。
• 因此，状态转移方程为： dp[i]=min⁡(dp[i],dp[i−coins[j]]+1)，其中 dp[i - coins[j]] 是凑出金额 i - coins[j] 需要的最少硬币数，+1 表示我们使用了一个面值为 coins[j] 的硬币。

3、初始状态

• 如果金额为 0，则不需要硬币，因此 dp[0] = 0。

4、无法凑出某个金额的处理

• 如果某个金额无法凑出，我们将 dp[i] 设为一个大于 amount 的值，这样在最后判断 dp[amount] 时可以得出无法凑出的结论。

（2）多维动态规划

1、不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

竟然，许久未见我居然做出来了哈哈哈哈哈哈哈哈哈哈哈哈（狂笑）

2、最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

（3）中心拓展法

1、最长回文子串

给你一个字符串 s，找到 s 中最长的 回文子串。

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        int maxLen=0,maxLeft=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<2;j++){
                int l=i,r=i+j;
                while(l>=0&&r<n&&s[l]==s[r]){
                    l--,r++;
                }
                l++,r--;
                if(maxLen<(r-l+1)){
                    maxLen=r-l+1;
                    maxLeft=l;
            	 }
            }
        }
        return s.substr(maxLeft,maxLen);
    } 
};

本题顾名思义，使用中心扩展法解决，则首先需要确定中心点，很容易思考得出一共有两种中心：一个字符和两个字符。

外层循环遍历中心点的位置，内层循环是确定是哪种中心。

当字符匹配时，l、r相应增减。直到不匹配为止，然后l、r需要回溯一位到回文串边界。

由l、r来确定回文串的起始位置和长度，并维护一个最大长度和相应的起始位置。

使用substring方法返回最长回文串。