713代码随想录--动态规划part06

322零钱兑换
装满量为j的最小物是dp[j]
递推公式 不放硬币i的次数加1，和放硬币i的次数取最小值

279完全平方和
完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
思路和上一题一样

139单词拆分
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
遍历顺序：组合问题是先遍历物品在遍历背包。排列问题是先编列背包在遍历物品
求组合数：动态规划：518.零钱兑换II (opens new window)
求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包） (opens new window)
求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数