详解一下动态规划，这里参考 labuladong 网站写的动态规划文章 .

动态规划 （Dynamic Programming）

文章：动态规划解题套路框架

视频：动态规划框架套路详解

MD数学公式：使用MD语法编写数学公式

放弃了一段时间动态规划，总感觉太难了， 现在迫不得已，还是需要捡起来，并掌握，哎，还是有一定的挑战 😢

就按照labuladong网站的思路学习。

一、动态规划基本技巧（20240219更新）

动态规划解题套路框架

我们都知道斐波那契数列的问题，核心的通项公式就是f(n) = f(n-1) + f(n-2)，但是这个过程会出现重复计算的问题，这个时候就需要使用备忘录来避免重复计算的问题。

学习动态规划的话，我们需要知道动态规划是什么？什么情况下会用到动态规划？动态规划求解有什么技巧没？如何学习动态规划？

1、

2、动态规划以前应用在求最值的问题上

3、动态规划的核心是什么？因为需要求最值， 我们不知道哪个情况下的是最值出现的地方，所有我们需要穷举所有的情况

4、穷举过程中就会面临的问题：会不会存在重叠子问题的情况？有没有最优子结构？

明确base case -> 明确[状态] -> 明确[选择] ->定义dp数组/函数的含义

代码框架：

自顶向下递归的动态规划

def dp(状态1, 状态2, ...):
  for 选择 in 所有可能的选择:
    # 此时的状态已经因为做了选择而改变
    result = 求最值(result, dp(状态1, 状态2, ...))
  return result

自底向上迭代的动态规划

# 初始化base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有的值:
  for 状态2 in 状态2的所有的值:
    for ...
    	dp[状态1][状态2][...] = 求最值(选择1, 选择2...)

509. 斐波那契数

使用备忘录来求解， 计算出来每一位斐波那契的值，保存下来。

自顶向下使用递归，自底向上使用迭代。

class Solution {
    public int fib(int n) {
        int[] memo = new int[n+1]; // 为什么是n+1位， 因为最后是直接返回的memo[n], 如果是n的话，数组会越界。
        return dp(memo, n);
    }

    public int dp(int[] memo, int n){
        if(n ==0 || n==1){  // 如果 0或者1 直接返回n
            return n;
        }
        if(memo[n] != 0){  // 如果不为0
            return memo[n];  // 直接返回
        }
        memo[n] = dp(memo, n-1) + dp(memo, n-2);  // 否则的话 计算memo[n]
        return memo[n];
    }
}

class Solution {
    public int fib(int n) {
        if(n == 0){  // 只有一个需要单独返回
            return 0;
        }
        int[] dp = new int[n+1];
        // base case
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

class Solution {
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        int dp0 = 0, dp1 = 1;  // 分别表示这dp[i-2] 和dp[i-1]
        for(int i=2;i<=n;i++){
            int dpn = dp0+dp1;

            dp0 = dp1;  // 动态的维护前面n-2和n-1的值
            dp1 = dpn;
        }
        return dp1;
    }
}

这里，引出状态转移方程这个名称，实际上就是描述问题结构的数学形式。

$$f(n) = \left\{ \begin{matrix} 1,n=1,2 \\ f(n-1) + f(n-2), n>2 \end{matrix} \right.$$

$f(n)$ 的函数参数会不断变化，所以可以把参数n想做是一个状态，这个状态n是有状态n-1和n-2状态相加而来的，这就叫做状态转移，仅此而已。

322. 零钱兑换

给你一个整数数组coins，表示不同面额的纸币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需要的最少的硬币个数，如果没有任何一种硬币组合能够组成总金额，返回-1.每种硬币的数量是无限的。

存在最优子问题，比如amount = 11， 那么， 10、9、6还是按照当时11一样的思路来解决。子问题和问题一样。硬币的数量也是无限的。

这里就套用labuladong在网站上写的迭代求解最值的框架

// define dp
int[] dp = new dp[amount+1];
Arrays.fill(dp, amount+1);  // 为啥都赋值为amoun+1
// base case 
dp[0] = 0;
// 
for(int i=0;i<dp.length;i++){  // 这里只用了下标，没有用里面的值， 下标就是表示需要凑成的钱
  for(int coin: coins){
    if(i-coin<0){  // 表示不能用这个硬币来凑
      continue;
    }
    dp[i] = Math.min(dp[i], 1+dp[i-coin]);  // 总金额 - 选择的金额求最小值
  }
}
return dp[amount] == amount+1 ? -1: dp[amount];

通项公式：

$$dp(n) = \left\{ \begin{matrix} 0, n=0 \\ -1,n<0 \\ min(dp(n-coin)+1 | coin \in coins), n>0 \end{matrix} \right.$$

就是说amount=0时结果等于0， amount<0时结果-1， amount>0的时候就是求最小值。

最后总结

也算是断断续续的看完了这一篇文章，还是对动态规划有了一定的了解，说解题还说不上，现在能根据题解看懂思路了，还是蛮不容易的，后面就是找一些例题来做，巩固一下思路。

我们后面还有很多篇文章，就这些就够我看很久的了。

这里说明一下，这篇文章展示没有做整理，是在我看文章的时候的一个笔录，可能有些地方不严谨。

二、动态规划设计：最长递增子序列（20240220更新）

原文章地址：动态规划设计：最长递增子序列

终于进入到了第二篇文章的学习 ，挺进大别山。

数学归纳法

最长递增子序列（Longest Increasing Subsequence简称LIS)是非常经典的一个算法问题，容易想到动态规划，$O(n^2)$ 的时间复杂度。

子序列和子串的概念。子序列不一定是连续的，子串一定是连续的。

dp[i]表示什么？表示前i个元素最长的递增子序列？？（猜对了一半）

我们会这样定义：dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。

// dp
int[] dp  = new int[nums.length+1];
// base case
dp[0] = 1;  // 最少都是他自己一个

所以根据这个定义我们知道，最后求解就是dp中最大的值

int ans = 0;
for(int res: dp){
  ans = Math.max(ans, res);
}
return ans;

如何设计算法逻辑进行状态转移？

假如我们已经知道了dp[0..4]的所有结果，我们如何通过这些一直推到dp[5]?

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for(int i=0;i<nums.length;i++){  // 循环选择1
            for(int j=0;j<i;j++){  // 循环选择2
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[i], 1 + dp[j]);  // 求前面的最大值
                }
            }
        }
        int ans = 0;
        for(int i = 0;i<dp.length;i++){
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

今天还是继续来做这个动态规划的题。

上面的题大概就是从前面找到小于当前值的数，比如是dp[i]，然后用dp[i]和1+dp[i+1]比较求最大值。

三、最优子结构原理和du数组遍历方向（20240221更新）

不说啥今天是第三天了，继续搞动态规划。今天力扣里面的竞赛分数更新了，这是我有时以来得一次有分数有排名，为啥开始分数是1430？可能是因为之前报名了周赛，但是么有去参加，给从1500分扣下来了，不过没关系，我感觉这次一定会坚持下来。

原文章地址：最优子结构原理和 dp 数组遍历方向

当前文章大致说明了几个问题。

一个是最优子结构的问题，如果不满足最优子结构，可以在一定情况下转化成最优子结构；

第二个就是dp的数组长度是n还是n+1， 我们应该习惯定义成n+1的长度，将下表为0的位置留出来。

第三个就是dp数组的遍历方向，这里主要是要看base case，我们需要根据已经算出来的dp值来构建转移方程。