.net 網(wǎng)站開發(fā)教程中山谷歌推廣
前言
###我做這類文章一個重要的目的還是給正在學(xué)習(xí)的大家提供方向(例如想要掌握基礎(chǔ)用法,該刷哪些題?建議靈神的題單和代碼隨想錄)和記錄自己的學(xué)習(xí)過程,我的解析也不會做的非常詳細(xì),只會提供思路和一些關(guān)鍵點(diǎn),力扣上的大佬們的題解質(zhì)量是非常非常高滴!!!
習(xí)題
1.組合總和IV
題目鏈接:377. 組合總和 Ⅳ - 力扣(LeetCode)
題面:
記憶化搜索+遞歸:
class Solution {int[] nums;int[] flag;public int combinationSum4(int[] nums, int target) {this.nums = nums;flag = new int[target+1];Arrays.fill(flag,-1);return recursion(target);}public int recursion(int i){if(i==0)return 1;if(flag[i]!=-1)return flag[i];int sum = 0;for(int a:nums){if(a<=i){sum+=recursion(i-a);}}return flag[i] = sum;}
}
遞推:
class Solution {public int combinationSum4(int[] nums, int target) {int[] flag = new int[target+1];flag[0] = 1;for(int i = 1;i<=target;i++){for(int a:nums){if(a<=i){flag[i]+=flag[i-a];}}}return flag[target];}
}
?2.統(tǒng)計(jì)構(gòu)造好字符串的方案數(shù)
題目鏈接:2466. 統(tǒng)計(jì)構(gòu)造好字符串的方案數(shù) - 力扣(LeetCode)
題面:
代碼:
class Solution {public int countGoodStrings(int low, int high, int zero, int one) {int[] flag = new int[high+1];flag[0] = 1;int mod = (int)1e9+7;for(int i = 1;i<=high;i++){if(i>=zero){flag[i]=(flag[i-zero]+flag[i])%mod;}if(i>=one){flag[i]=(flag[i-one]+flag[i])%mod;}}int ans = 0;for(int i = low;i<=high;i++){ans = ans+ flag[i];ans%=mod;}return ans;}
}
后言
上面是動態(tài)規(guī)劃相關(guān)的習(xí)題,共勉
?