題目描述

    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， 遞歸的對(duì)象是完全平方數(shù)集合，以及要尋找的數(shù)集list[0...i]（=n-table[0...i]）

    1. 找出小于目標(biāo)數(shù)：n的完全平方數(shù)，如果找到直接返回

    2. 進(jìn)行BFS（完全平方數(shù)集合:table，要尋找的數(shù)集:list，層數(shù):depth）：

    循環(huán)table,針對(duì)每個(gè)小于當(dāng)前n的完全平方數(shù)，求出它要尋找的數(shù)集：x={n-table[i]} , i∈[0,table.Count] => 得到list

    實(shí)現(xiàn)代碼

public class Solution {    public int NumSquares(int n)     {       if(n == 1){		return 1;	}		var len = n/2;	var depth = 1;	var table = new List<int>();	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<int>();	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<int>table , IList<int>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<int>();	for(var i = 0;i < target.Count; i++){		var t = table.Where(x=>x<target[i]).tolist(); j="0;j" pre="" var=""></p></target[i]).tolist();></int></int></int></int></int>