leetcode 72.编辑距离

1. 思路

我们可以对任意一个单词进行三种操作：

• 插入一个字符；
  
• 删除一个字符；
  
• 替换一个字符。

初始状态


动态转移方程

• 如果A和B最后一个字母相同:

• 如果A和B最后一个字母不同：

2. 代码

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int dp[][] = new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            dp[i][0] = i;
        }
        for(int i=1;i<=len2;i++){
            dp[0][i] = i;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                }
            }
        }
        return dp[len1][len2];
    }
}

leetcode 121.买卖股票的最佳时机

1. 思路

• 动态规划

表示第i天卖股票的最大利润

• 初始状态

• 动态转移方程

2. 代码

class Solution {
public int maxProfit(int[] prices) {
    int res = 0;
    int len = prices.length;
    int dp[] = new int[len];
    dp[0] = 0;
    for(int i=1;i<len;i++){
       dp[i] = Math.max(dp[i-1]+prices[i]-prices[i-1],0);
       res = Math.max(dp[i],res);
    }
    return res;
  }
}

leetcode 122.买卖股票的最佳时机II

可以多次买卖，获取最大利润

1. 思路

累加所有的利润price[i]-price[i-1]在一起，就是最大利润。

2. 代码

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

leetcode 123.买卖股票的最佳时机III

最多完成两笔交易，达到最大利润。

1. 思路

• 定义两个动态转移数 len表示天数，k表示完成了几笔交易
• 初始化
  • 
  • 
  • 
• 状态转移方程

2. 代码

class Solution {
public int maxProfit(int[] prices) {
            int k = 2;
            int len = prices.length;
            int[][] hold = new int[len][k+1];
            int[][] sell = new int[len][k+1];
            for(int i=0;i<=k;i++){
                sell[0][i] = hold[0][i] = Integer.MIN_VALUE/2;
            }

            hold[0][0] = -prices[0];
            sell[0][0] = 0;

            for(int i=1;i<len;i++){
                hold[i][0] = Math.max(hold[i-1][0],sell[i-1][0]-prices[i]);
                for(int j=1;j<=k;j++) {
                    hold[i][j] = Math.max(hold[i - 1][j], sell[i - 1][j] - prices[i]);
                    sell[i][j] = Math.max(sell[i - 1][j], hold[i - 1][j-1] + prices[i]);
                }
            }
        return Arrays.stream(sell[len - 1]).max().getAsInt();
    }
}