算法集训营第二期｜多做多想

提纲

1.学习方法：多做 格物致知；多想 培养抽象思维
2.学习的内容，自己的学习进度
3.已经想明白了一些的题目，以及其变种情况

前言

确实拖延咯，集训营已接近尾声，自己该做做面试的思想准备。第五周接触的动态规划，课程里列举的题型算是之前学习思考的集大成者（有部分题目还没想通），课程里介绍了很多典型题，什么杨辉三角咯，什么背包咯，自己实际只想了想某几道题的思路。下面将从老师介绍的学习法宝、自己的学习进度汇报、以及思考过的题目简单记录下。

一、学习法宝

涵老师说这部分的内容比较难，但却是面试考察的“重灾区”，需要我们注意学习的方式：一是多做题，多亲笔敲代码，手画每一步状态图；二是多想，比如挑选一系列动态规划题，先不手写代码，专注想“状态转移方程”，并和正确答案进行对照。

二、学习进度

杨辉三角比较熟悉，零钱兑换系列的问题想了很久，因为看不懂课程里的教学思路和示例代码（课程写得很棒，每个示例题目都很有代表性，还明显的对上几周的知识有关联性和继承性，由浅入深、登堂入室；但自己缺乏抽象思维，想象不出数据变化的过程），只好把数组值变化的每一步骤都画了出来，然后再去反推状态转移方程里的每一个代码是什么意思，也就是通过零钱兑换的题突然想到，动态规划用在这里，是基于在这最后一步操作时，之前解决过的子问题的解决方案数在当前状态下为定值的前提条件——可以理解为自己创建的N维数组，在走到最后一个格子（答案）时，之前的每一步，都是在算当前状态子问题的解决方案数，为后来的格子引用子问题解决方案作“铺垫”。

动态规划（英語：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

【图 2.1 518 零钱兑换 II 手写dp值变化 ｜ 测试用例 amount = 5, coins = [1, 2, 5]】

三、思考过的题目

322. 零钱兑换
518. 零钱兑换 II
118. 杨辉三角
417. 太平洋大西洋水流问题

原文地址：《算法集训营第二期｜ 学习二叉树》 2022-01-06