【算法】动态规划

一.动态规划三大步骤

首先,动态规划就是利用历史记录,来避免我们重复计算,我们需要使用一位数组或者二维数组来保存。

第一步骤：定义元素的含义，我们在开头提到过，我们可以使用一位数组或者二维数组来保存历史数据。现在我们假设使用一个一维数组来保存数据，这时一个非常重要的点就是规定你所创建的这个数组的含义，例如你创建了一个一维数组dp[]，这个dp[i]是代表什么意思呢？

第二步骤：找出数组元素之间的关系式，动态规划你可以理解为我们之前学习过的归纳法，当我们要计算dp[n]时，我们可以利用dp[n-1],dp[n-2]....dp[1]来推出dp[n]的，也就是可以理解为我们可以通过历史数据来推算出新的元素的值，所以找出数组元素之间的关系式是非常重要的。例如dp[n]=dp[n-1]+dp[n-2],这个就是数组元素之间的关系式。

第三步骤：找出初始值，通过数学归纳法我们可以知道，找出数组元素之间的关系式，例如我在步骤二中提到的例子dp[n]=dp[n-1]+dp[n-2],我们可以通过dp[n-1]和dp[n-2]来算出我们所需要的dp[n],同理我们要得出dp[n-1]和dp[n-2]的值同样要通过前两项来推算获取其相应的值，一直推算下去dp[3]=dp[2]+dp[1],我们已经无法对dp[1]和dp[2]进行分解，所以我们必须提前获取dp[1]和dp[2]的值，这就是我们要找到的初始值。

有了初始值和数组元素之间的关系式，我们就可以得到dp[n]的值，在步骤一中就提到定义元素的含义，这样我们就可以解决问题了。

二.LeetCode习题分析

2.1动态规划--买卖股票的最佳时机

2.1.1121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

第一步：我们可以这样分析这个题目，假设在第i天时，我们会遇到两种情况，1.是我们手中持有股票，即dp[i][0]：表示第i天持有股票能获取的最大利润，2.是我们手中没有持有股票，即dp[i][1]：表示第i天不持有股票能获取的最大利润。

第二步：找出数组元素之间的关系式。

我们要得到dp[i][0]，即第i天持有股票能获取的最大利润，显然有两种情况，第一种是第i-1天就持有股票，根据提议你只能选择某一天买入这只股票，那么第i天的股票将来源于第i-1天，即数组元素之间的关系式为dp[i][0]=dp[i-1][0]。第二种情况是第i-1天不持有股票，那么由题意得股票只能是当天买入的，即数组元素之间的关系式为dp[i][0]=-prices[i]。然后我们在这两种情况中选择出较大的那一个即可。Math.max(dp[i-1][0],-prices[i])。

我们要得到dp[i][1]：表示第i天不持有股票能获取的最大利润。，同样也有两种情况，一种是第i-天就没有持有股票，那正好我们啥也不用做，即dp[i][1]=dp[i-1][1]；另一种是第i-1天持有股票，需要我们在今天把他卖出，即dp[i][1]=dp[i-1][0]+prices[i]。我们只需要选择这两种情况种较大的那一种即可，dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i])。

第三步：找出初始值

由第二步我们找出的数组元素之间的关系式我们可以得出，要想最终解决这个问题，我们需要知道dp[0][1]和dp[0][0]的值。

dp[0][0]：第0天持有股票获得的最大利润，显然持有股票意味着要花钱买入，所以dp[0][0]=-prices[0]；
dp[0][1]：第0天不持有股票获得的最大利润，不持有股票有两种情况，一是没有买入股票，二是已经卖出股票(同一天买入和卖出，dp[0][0]=0)，两种情况dp[0][1]都等于0，即dp[0][1]=0。

代码展示：

package com.algo.test;
 
public class Solution121A {
    public int maxProfit(int[] prices){
        int length = prices.length;
        //确定dp数组
        int[][] dp =new int[length][2];
        //dp数组的初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[length-1][1];
    }
}

2.1.2122. 买卖股票的最佳时机 II

2.1.3123. 买卖股票的最佳时机 III

2.2动态规划--最长回文子串

5. 最长回文子串 

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成