一维动态规划

**1137. 第 N 个泰波那契数（入门）**

public int tribonacci(int n) {
    if(n == 0) return 0;
    if(n == 1 || n == 2) return 1;
    int[] res = new int[n + 1];
    res[0] = 0;
    res[1] = 1;
    res[2] = 1;
    for(int i = 3; i < n + 1; i++) {
        res[i] = res[i - 1] + res[i - 2] + res[i - 3];
    }
    return res[n];
}

746. 使用最小花费爬楼梯

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = cost[0];
    for(int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i - 1];
    }
    return Math.min(dp[n], dp[n -1]);
}

198. 打家劫舍

public int rob(int[] nums) {
    int n = nums.length;
    if(n == 1) return nums[0];

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = nums[0];
    dp[2] = nums[1];
    int max = 0;
    for(int i = 3; i <= n; i++) {
        dp[i] = Math.max(dp[i - 2], dp[i - 3]) + nums[i - 1];
    }
    // System.out.println(Arrays.toString(dp));
    return Math.max(dp[n], dp[n-1]);
}

**790. 多米诺和托米诺平铺（找递推式）**

long[] f = new long[1005];
long MOD = (long)1e9 + 7;
public int numTilings(int n) {

    f[0] = 1;
    f[1] = 1;
    f[2] = 2;
    for(int i = 3; i <= n; i++) {
        f[i] = (f[i-1] * 2 + f[i-3]) % MOD;
    }
    return (int)f[n];
}

多维动态规划

**62. 不同路径（多维入门）**

class Solution {
    public int uniquePaths(int m, int n) {
        // 1. 定义动态规划 每个点为到这个点的路径
        int[][] map = new int[m][n];
        // 2. 初始化数组
        for(int i = 0; i < m; i++) map[i][0] = 1;
        for(int j = 0; j < n; j++) map[0][j] = 1;
        // 3. 状态转移
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                map[i][j] = map[i - 1][j] + map[i][j - 1];
            }
        }
        return map[m - 1][n - 1];
    }
}

**1143. 最长公共子序列（状态转移方程掌握）**

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(chars1[i - 1] == chars2[j - 1]) 
                    dp[i][j] = dp[i-1][j-1] + 1;
                else 
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
}

**714. 买卖股票的最佳时机含手续费（一个新的角度）**

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

**72. 编辑距离（经典题目）**

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0; i <= m; i++) dp[i][0] = i;
        for(int j = 0; j <= n; j++) dp[0][j] = j;

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s1[i - 1] == s2[j - 1]) 
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    int min = Math.min(dp[i][j-1], dp[i-1][j]);
                    dp[i][j] = Math.min(min, dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}