针对279题使用动态规划求解

来源：4-2 map的使用 Intersection of Two Arrays II

哈哈哈蜜瓜

2018-02-08

受老师提示用动规自底向上的方式去解了一遍279题，在leetcode也AC了，但是这种写法感觉跟老师你解出来的动规似乎有点不一样= =请老师判断下我这么写算不算动规，如果不是应该如何改进才算

写回答

1回答

liuyubobobo

2018-02-09

已采纳

不算是动态规划，一个标准的BFS求最短路径的解法。印象里课程的6-5介绍的就是这种方法？可以和课程的代码比较一下看看。

整体来说，你在求解问题的时候，没有定义状态，没有定义状态转移方程，没有利用状态的重叠子问题和最优子结构，就不是动态规划。

liuyubobobo

哈哈哈蜜瓜

f(n-i*i)不是状态转移方程，因为没有转移。这个问题的动态规划解法可以参考这里，看看你是否能够想明白？https://github.com/liuyubobobo/Play-Leetcode/blob/master/0279-Perfect-Squares/cpp-0279/main3.cpp

2018-02-09

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1