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

Question

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

Answer 1

liuyubobobo 2018-02-09 01:39:44

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

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

• 提问者 哈哈哈蜜瓜 #1

  那老师您看看我这样的思路是否可行：定义状态在n以内找出所有i的平方不超出n的值，然后状态转移方程就是f(n-i*i)，但是往下面就没思路了= =

• liuyubobobo 回复 提问者 哈哈哈蜜瓜 #2

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