云服务器如何安装网站,国家职业技能培训官网,门户网站构建,互联网运营是什么工作提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣279. 完全平方数二、力扣139. 单词拆分 前言 这篇背包问题总结篇是对背包问题的高度概括#xff0c;讲最关键的两部#xff1a;递推公式和遍历顺序文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣279. 完全平方数二、力扣139. 单词拆分 前言 这篇背包问题总结篇是对背包问题的高度概括讲最关键的两部递推公式和遍历顺序结合力扣上的题目全都抽象出来了。 而且每一个点我都给出了对应的力扣题目。
一、力扣279. 完全平方数
class Solution {public int numSquares(int n) {int[] dp new int[n1];if(n 3){return n;}Arrays.fill(dp,Integer.MAX_VALUE);dp[0] 0;for(int i 1; i 100; i ){for(int j 1; j n; j ){if(j i*i){dp[j] Math.min(dp[j],dp[j-i*i]1);}}}return dp[n];}
}二、力扣139. 单词拆分
class Solution {public boolean wordBreak(String s, ListString wordDict) {boolean[] dp new boolean[s.length()1];dp[0] true;for(int i 1; i s.length(); i ){for(int j 0; j wordDict.size(); j ){String temp wordDict.get(j);if(itemp.length() dp[i-temp.length()] fun(s,temp,i-temp.length())){dp[i] true;}}}return dp[s.length()];}boolean fun(String s1,String s2,int index){for(int i 0; i s2.length(); i ){if(s1.charAt(iindex) ! s2.charAt(i)){return false;}}return true;}
}
