动态规划问题

看一遍就理解：动态规划详解

- 什么样的问题可以考虑使用动态规划解决呢？

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。
比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。

- 动态规划的解题思路

动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。 并且动态规划一般都是自底向上的。

1. 穷举分析
2. 确定边界
3. 找出规律，确定最优子结构
4. 写出状态转移方程

dp[0][0][...] = 边界值
for(状态1 ：所有状态1的值){
    for(状态2 ：所有状态2的值){
        for(...){
          //状态转移方程
          dp[状态1][状态2][...] = 求最值
        }
    }
}
1
2
3
4
5
6
7
8
9

• 求解最大子段和

public static void main(String[] args) {
        int[] arr = new int[] {-1, 16, 1, -2, 3, -22, 1, -2, 4};
        System.out.println(maxSubArray(arr));
    }

    private static int maxSubArray(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        int max = arr[0];
        int sum = 0;
        for (int e : arr) {
            sum = (sum > 0 ? sum : 0) + e;
            max = Math.max(max, sum);
        }
        return Math.max(max, 0);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 青蛙跳问题
  一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

// f(n) = f(n-1) + f(n-2)
public class Solution {
        public int numWays(int n) {
            if (n <= 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            int a = 1;
            int b = 2;
            int temp = 0;
            for (int i = 3; i <= n; i++) {
                temp = (a + b) % 1000000007;
                a = b;
                b = temp;
            }
            return temp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 最长严格递增子序列的长度

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        //初始化就是边界情况
        dp[0] = 1;
        int maxans = 1;
        //自底向上遍历
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            //从下标0到i遍历
            for (int j = 0; j < i; j++) {
                //找到前面比nums[i]小的数nums[j],即有dp[i]= dp[j]+1
                if (nums[j] < nums[i]) {
                    //因为会有多个小于nums[i]的数，也就是会存在多种组合了嘛，我们就取最大放到dp[i]
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            //求出dp[i]后，dp最大那个就是nums的最长递增子序列啦
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26