算法框架
1 树
2 DP
eg. 凑零钱
def CoinChange(coins: List[int], amount: int):def dp(n):# 终止条件if n == 0: return 0if n < 0: return -1res = float('INF')for coin in coins:subproblem = dp(n - coin)# 子问题无解情况if subproblem == -1: continueres = min(res, 1 + subproblem)return res if res != float('INF') else -1return dp(amount)
DP某些情况下可以理解为一颗树的遍历
3 回溯
void backtrack(int[] nums, LinkedList<Integer> track)
{if (track.size() == nums.length) {res.add(new LinkedList(track));return;}for (int i = 0; i < nums.length; ++i) {if (track.contains(nums[i])) {continue;}track.add(nums[i]);// 进入下一层决策树backtrack(nums, track);track.removeList();
}// 提取N叉树遍历框架
void backtrack(int[] nums, LinkedList<Integer> track)
{for (int i = 0; i < nums.length; ++ i) {backtrack(nums, track);}
}
回溯算法就是一个N叉树的前序+后序遍历fd
