How many squares, cubes, fourth powers, etc. do I need to sum to n?
Mathematica 61 50 bytes
With 11 bytes saved by LegionMammal978.
When restricted to powers of counting numbers, this problem is straightforward (in Mathematica).  When extended to include powers of integers, it's a nightmare.
(k=0;While[PowersRepresentations[#,++k,#2]=={}];k)&amp;


Test Cases
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[7, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[4, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[7, 3]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &amp;[23, 3]


4
1
7
9


PowersRepresentationsp[n,k,p] finds all the cases in which n can be expressed as a sum of k positive integers raised to the p-th power.

For example,
PowersRepresentations[1729, 2, 3]


{{1, 12}, {9, 10}}

Checking,
1^3 + 12^3


1729


9^3 + 10^3


1729