本博客是记录作者做动态规划算法的简单、中等难度的背包问题的笔记。

LeetCode题目 相关题目类型 题目类型分析 题目思路 相关链接
0416 分割等和子集（中等难度）     416. 分割等和子集 - 力扣（LeetCode） (leetcode-cn.com)
1049 最后一块石头的重量II（中等难度）     1049. 最后一块石头的重量 II - 力扣（LeetCode） (leetcode-cn.com)
0494 目标和（中等难度）     494. 目标和 - 力扣（LeetCode） (leetcode-cn.com)
0474 一和零（中等难度）     474. 一和零 - 力扣（LeetCode） (leetcode-cn.com)
0518 零钱兑换II（中等难度）     518. 零钱兑换 II - 力扣（LeetCode） (leetcode-cn.com)
0377 组合总和IV（中等难度）     377. 组合总和 Ⅳ - 力扣（LeetCode） (leetcode-cn.com)
0070 爬楼梯（简单难度）     70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)
0322 零钱兑换（中等难度）     322. 零钱兑换 - 力扣（LeetCode） (leetcode-cn.com)
0279 完全平方数（中等难度）     279. 完全平方数 - 力扣（LeetCode） (leetcode-cn.com)
0139 单词拆分（中等难度）     139. 单词拆分 - 力扣（LeetCode） (leetcode-cn.com)

121 买卖股票的最佳时机

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

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、确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5、举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

以上我们用动规的方法分析完了，C++代码如下：

int fib(int n) {
        /*输入一个整数，输出一个整数*/
        if(n<=1){
            return n;
        }
        vector<int> dp(n+1); //第i个数的斐波那契数值是dp[i]
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            dp[i] =  dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列。代码如下：

int fib(int n) {
        /*输入一个整数，输出一个整数*/
        if(n<=1){
            return n;
        }
        vector<int> dp(2); //第i个数的斐波那契数值是dp[i]
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            int temp = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return dp[1];
    }