LeetCode -- Perfect Squares

LeetCode -- Perfect Squares

題目描述
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.


For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.


Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.


思路：
本題還是BFS， 遞歸的對象是完全平方數集合，以及要尋找的數集list[0...i]（=n-table[0...i]）






1. 找出小於目標數：n的完全平方數，如果找到直接返回
2. 進行BFS（完全平方數集合:table，要尋找的數集:list，層數:depth）：
循環table,針對每個小於當前n的完全平方數，求出它要尋找的數集：x={n-table[i]} , i∈[0,table.Count] => 得到list


實現代碼

public class Solution {
    public int NumSquares(int n) 
    {
       if(n == 1){
		return 1;
	}
	
	var len = n/2;
	var depth = 1;
	var table = new List();
	for(var i = 1;i <= len; i++){
		var x = i * i;
		if(x == n){
			return 1;
		}
		if(x < n){
			table.Add(x);
		}
	}
	
	
	var list = new List();
	for(var i = 0 ;i < table.Count; i++){
		list.Add(n-table[i]);
	}
	
	Bfs(table, list, depth + 1);
	
	return Depth;
}


private int Depth;
private bool Found = false;


public void Bfs(IList table , IList target , int depth)
{
	if(Found){
		return;
	}
	
	for(var i =0 ;i < table.Count; i++){
		for(var j = 0;j < target.Count; j++){
			if(table[i] == target[j]){
				Depth = depth;
				Found = true;
				return;
			}
		}
	}
	
	var list = new List();
	for(var i = 0;i < target.Count; i++){
		var t = table.Where(x=>x