代码随想录1刷--day9 动态规划

动态规划

• 基���题目
  • 509 斐波那契数
  • 70 爬楼梯
  • 746 使用最小花费爬楼梯
  • 62 不同路径
  • 63 不同路径II
  • 343 整数拆分
  • 96 不同的二叉搜索树
  • 背包问题
    • 01背包
      • 0416 分割等和子集
      • 1049 最后一块石头的重量II
      • 0494 目标和
      • 0474 一和零
      • 完全背包
        • 0518 零钱兑换II
        • 0377 组合总和IV
        • 0070 爬楼梯
        • 0322 零钱兑换
        • 0279 完全平方数
        • 0139 单词拆分
        • 多重背包
        • 打家劫舍
          • 198 打家劫舍
          • 213 打家劫舍II
          • 337 打家劫舍III
          • 股票问题
            • 121 买卖股票的最佳时机(只能买买一次)
            • 122 买卖股票的最佳时机II(可以买卖多次)
            • 123 买卖股票的最佳时机III(最多买卖两次)
            • 188 买卖股票的最佳时机IV(最多买卖k次)
            • 309 买卖股票的最佳时期含冷冻期(T+1)
            • 714 买卖股票的最佳时机含手续费(买卖多次，每次有手续费)
            • 子序列问题
              • 子序列(不连续)
                • 300 最长上升子序列
                • 1143 最长公共子序列
                • 1035 不相交的线
                • 子序列(连续)
                  • 674 最长连续递增序列
                  • 718 最长重复子数组
                  • 53 最大子序和
                  • 编辑距离
                    • 392 判断子序列
                    • 115 不同的子序列
                    • 583 两个字符串的删除操作
                    • 72 编辑距离
                    • 回文
                      • 647 回文子串
                      • 516 最长回文子串

                        动态规划理论基础

                        动态规划，英文：Dynamic Programming, 简称DP，如果某个问题有很多重叠子问题，使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的。

                        （）

                        动态规划的解题步骤（动态规划五部曲）

                        1. 确定dp数组以及下标含义
                        2. 确定递推公式
                        3. dp数组如何初始化
                        4. 确定遍历顺序
                        5. 举例推导dp数组

                        做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

                        （）

                        基础题目

                        • 509 斐波那契数列

                          // 1. 确定dp数组以及下标含义：dp[i]定义为第i个数的值为dp[i]// 2. 确定递推公式:dp[i] = dp[i-1]+dp[i-2]// 3. dp数组如何初始化: dp[0]=0; dp[1]=1;// 4. 确定遍历顺序:从前往后遍历// 5. 举例推导dp数组class Solution {public:    int fib(int n) {        if(n