class DP
{
public:
    DP();
    ~DP();

public:
    // 问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
    int jumpFloor(int number);

    // 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）
    // 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）
    // 问总共有多少条不同的路径？
    //https://leetcode-cn.com/problems/unique-paths/submissions/
    int uniquePaths(int m, int n);

    //给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
    //说明：每次只能向下或者向右移动一步。
    //https://leetcode-cn.com/problems/minimum-path-sum/
    int minPathSum(vector<vector<int>>& grid);

    //https://leetcode-cn.com/problems/edit-distance/
    //给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
    //  你可以对一个单词进行如下三种操作：
    //插入一个字符
    //删除一个字符
    //替换一个字符
    //来源：力扣（LeetCode）
    //链接：https ://leetcode-cn.com/problems/edit-distance
    int minDistance(string word1, string word2);

    //给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
    //  如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
    //  注意：你不能在买入股票前卖出股票。
    //  来源：力扣（LeetCode）
    //  链接：https ://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
    //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    int maxProfit(vector<int>& prices);

    //https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
    //给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
    //  你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
    //  返回获得利润的最大值。
    //  注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
    //定义二维数组 dp[n][2]dp[n][2]dp[n][2]：
    //  dp[i][0]dp[i][0]dp[i][0] 表示第 iii 天不持有可获得的最大利润；
    //  dp[i][1]dp[i][1]dp[i][1] 表示第 iii 天持有可获得的最大利润（注意是第 iii 天持有，而不是第 iii 天买入）。
    //  定义状态转移方程：
    //  不持有：dp[i][0] = max(dp[i?1][0], dp[i?1][1] + prices[i]?fee)dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)dp[i][0] = max(dp[i?1][0], dp[i?1][1] + prices[i]?fee)
    //  对于今天不持有，可以从两个状态转移过来：1.昨天也不持有；2.昨天持有，今天卖出。两者取较大值。
    //  持有：dp[i][1] = max(dp[i?1][1], dp[i?1][0]?prices[i])dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])dp[i][1] = max(dp[i?1][1], dp[i?1][0]?prices[i])
    //  对于今天持有，可以从两个状态转移过来：1.昨天也持有；2.昨天不持有，今天买入。两者取较大值。
    //  作者：sweetiee
    //  链接：https ://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/jian-dan-dpmiao-dong-gu-piao-mai-mai-by-tejdo/
    //来源：力扣（LeetCode）
    //  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    int maxProfit(vector<int>& prices, int fee);

    //309. 最佳买卖股票时机含冷冻期
    //  给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

    //  设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票） :

    //你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    //  卖出股票后，你无法在第二天买入股票(即冷冻期为 1 天)。
//https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
    int maxProfit3(vector<int>& prices);

    int maxProfit4(vector<int>& prices);


    //https://leetcode-cn.com/problems/isomorphic-strings/
    // 同构字符串
    //给定两个字符串 s 和 t，判断它们是否是同构的。
    //  如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
    //  所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
    //  来源：力扣（LeetCode）
    //  链接：https ://leetcode-cn.com/problems/isomorphic-strings
    bool isIsomorphic(string s, string t);

    //给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    string longestPalindrome(string s);

    //给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    int maxSubArray(vector<int>& nums);
};

int DP::jumpFloor(int number)
{
    if (number <= 2)
    {
        return number;
    }
    // 定义数组元素来保存历史数据
    int* dp = new int[number + 1];

    // 找出初始值
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

    //通过关系式来计算出 dp[n]
    for (int n = 3; n <= number; n++)
    {
        dp[n] = dp[n - 1] + dp[n - 2];
    }
    return dp[number];
}

int DP::uniquePaths(int m, int n)
{
    if (m <= 0 || n <= 0)
    {
        return 0;
    }
    // 定义二位数组
    vector<vector<int> >dp(m, vector<int>(n));
    for (int i = 0; i < m; i++)
    {
        dp[i][0] = 1;
    }

    // 因为当m=0或n=0时，走的步数时固定的
    for (int i = 0; i < n; i++)
    {
        dp[0][i] = 1;
    }

    // 找到关系式,因为
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

int DP::minPathSum(vector<vector<int>>& grid)
{
    if (grid.size() <= 0 || grid[0].size() <= 0)
    {
        return 0;
    }
    int m = grid.size();
    int n = grid[0].size();

    // 关系式，和
    std::vector<std::vector<int>>dp(m, vector<int>(n));

    // dp[i][j]:走到i,j时的最小值
    // dp[i][j]=min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
    // 找到关系式,因为当m=0 或n=0时不能使用这种关系式
    // 初始值
    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; i++)
    {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    for (int j = 1; j < n; j++)
    {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (dp[i - 1][j] < dp[i][j - 1])
            {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            }
            else
            {
                dp[i][j] = dp[i][j - 1] + grid[i][j];
            }
        }
    }

    return dp[m - 1][n - 1];
}

int DP::minDistance(string word1, string word2)
{
    // 使用动态规划等的解法

    //1、定义动态数组的含义:
    // 若将cat变成cate,需要增加一个字符，或删除一个字符
    // 若将cat 变成fat,需要变换一个字符
    // 含义：通过分析知道，若将字符A的前i个字符，变换成字符B的前j个字符所需要的最少次数
    int m = word1.size();
    int n = word2.size();
    std::vector<std::vector<int>>dp(m + 1, std::vector<int>(n + 1));

    //2、找到数组之间的关系式
    // dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1;
    // 若word1[i] = word2[j]则不需要变换，所以 dp[i][j]=dp[i-1][j-1]

    //3、初始值
    for (int i = 1; i < m + 1; i++)
    {
        dp[i][0] = dp[i - 1][0] + 1;
    }
    for (int j = 1; j < n + 1; j++)
    {
        dp[0][j] = dp[0][j - 1] + 1;
    }

    for (int i = 1; i < m + 1; i++)
    {
        for (int j = 1; j < n + 1; j++)
        {
            if (word1[i - 1] == word2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                int a = dp[i - 1][j - 1];
                int b = dp[i - 1][j];
                int c = dp[i][j - 1];

                int temp = a < b ? a : b;
                dp[i][j] = (temp < c ? temp : c) + 1;
            }
        }
    }

    return dp[m][n];
}

int DP::maxProfit(vector<int>& prices, int fee)
{
    //1、动态数组第i天买入，第j天卖出的最大利润
    int m = prices.size();
    if (m <= 0)
    {
        return 0;
    }
    std::vector<std::vector<int>>dp(m, std::vector<int>(2));

    // 对股票有两种状态，持有的最大收益
    // 不持有的最大收益
    dp[0][0] = 0;// 第一天不持有
    dp[0][1] = -prices[0];//第一天持有

    for (int i = 1; i < m; i++)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

    }
    return dp[m - 1][0];
}

int DP::maxProfit(vector<int>& prices)
{
    //int n = (int)prices.size(), ans = 0;
    //for (int i = 0; i < n; ++i) {
    //  for (int j = i + 1; j < n; ++j) {
    //      ans = max(ans, prices[j] - prices[i]);
    //  }
    //}
    //return ans;


    if (prices.empty())
    {
        return 0;
    }
    int max = 0;
    int min_pre = prices[0];
    for (int i = 1; i < prices.size(); i++)
    {
        if (min_pre > prices[i])
        {
            min_pre = prices[i];
        }

        if (max <= (prices[i] - min_pre))
        {
            max = prices[i] - min_pre;
        }

    }

    return max;
}

int DP::maxProfit3(vector<int>& prices)
{
    // 股票有三种状态的收益,买入，卖出，冷冻期
    int size = prices.size();
    if (size <= 0)
    {
        return 0;
    }
    vector<vector<int>>dp(size, vector<int>(3));

    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    dp[0][2] = 0;

    for (int i = 1; i < size; i++)
    {
        // 考虑第i天持有股票的最大收益:第i-1天持有股票，不卖，或者第i-1天没有股票，买入
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);

        // 考虑第i天没有股票，且处于冷冻期，则只能是第i-1天，持有股票，并且卖了
        dp[i][1] = dp[i - 1][0] + prices[i];

        // 考虑第i天没有股票，且不处与冷冻期，所以，只能是第i-1天处于冷冻期，或第i-1天持有股票
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
    }

    return max(dp[size - 1][1], dp[size - 1][2]);
}

int DP::maxProfit4(vector<int>& prices)
{

}

bool DP::isIsomorphic(string s, string t)
{
    unordered_map<char, char> s2t;
    unordered_map<char, char> t2s;
    int len = s.length();
    for (int i = 0; i < len; ++i) {
        char x = s[i], y = t[i];
        if ((s2t.count(x) && s2t[x] != y) || (t2s.count(y) && t2s[y] != x)) {
            return false;
        }
        s2t[x] = y;
        t2s[y] = x;
    }
    return true;
}

std::string DP::longestPalindrome(string s)
{
    //1、设字符串dp[i][j]:也就是s[i:j]是回文串
    // dp[i][j]=true  是回文串
    // dp[i][j]=false 不是回文串

    //2、找关系
    // 只有当 dp[i+1][j-1] 是回文串，且s[i]==s[j]时，dp[i][j] 才是回文串


    //3、边界条件
    // 当字符子串长度为1时 是回文串dp[0][0]=true
    // 当字符子串为长度为2时，若s[0]==s[1]时也是回文串

    // 4注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

    int length = s.length();
    vector<vector<int>>dp(length, vector<int>(length));
    string max_sub_str;
    for (int l = 0; l < length; l++)
    {
        // 注意这里是i+l,因为子串长度为l
        for (int i = 0; i + l < length; i++)
        {
            int j = i + l;
            if (l == 0)
            {
                // 考虑子串长度为1
                dp[i][j] = true;
            }
            else if (l == 1)
            {
                // 子串长度为2
                dp[i][j] = (s[i] == s[j]);
            }
            else
            {
                dp[i][j] = (dp[i + 1][j - 1]) && (s[i] == s[j]);
            }

            // 获取最长的
            if (dp[i][j] && (l + 1 > max_sub_str.size()))
            {
                max_sub_str = s.substr(i, l + 1);
            }
        }
    }
    return max_sub_str;
}

int DP::maxSubArray(vector<int>& nums)
{
    // 动态规划的解法dp[i]=max{dp[i-1]+num[i],num[i]}
    // 其中dp[i]为以第i个结尾的连续数组的最大和
    // 然后取各个位置最大和的最大值
    int size = nums.size();
    int max_sum = nums[0];
    vector<int>dp(size);
    dp[0] = nums[0];
    for (int i = 1; i < size; i++)
    {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);

        if (dp[i] > max_sum)
        {
            max_sum = dp[i];
        }
    }
    return max_sum;
}