菜鸡的原地踏步史03(◐‿◑)
每日一念
改掉自己想到哪写哪的坏习惯
一维动态规划
爬楼梯
class Solution {
/**
dp[i] 爬到第i个台阶有dp[i]种爬法
dp[i] - dp[i - 1] + 1 & dp[i - 2] + 2
*/
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
class Solution {
/**
res.get(i)表示第i层的数组
首尾设置为1
res.get(i).get(j) = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j)
*/
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
for(int i = 0; i < numRows; i++) {
for(int j = 0; j <= i; j++) {
if(j == 0 || j == i) {
path.add(1);
}
else {
path.add(0);
}
}
res.add(path);
path = new ArrayList();
}
for(int i = 2; i < res.size(); i++) {
for(int j = 1; j < res.get(i).size() - 1; j++) {
int val = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j);
res.get(i).set(j, val);
// System.out.println(res.get(i).get(j));
}
}
return res;
}
}
class Solution {
/**
dp[i]表示第i家能偷到的最高金额
dp[i] -- dp[i - 1], dp[i - 2] + nums[i - 1]
*/
// dp[nums.length]
public int rob(int[] nums) {
if(nums.length == 0) {
return 0;
}
if(nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);
}
// dp[nums.length + 1]
public int rob(int[] nums) {
if(nums.length == 0) {
return 0;
}
if(nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);
}
}
class Solution {
/**
dp[i] 组成和为i的完全平方数最少数量 -- dp[i - j *j]
从 < i 的第一个完全平方数开始找
dp数组需要的最长长度为n + 1
3 = 1 + 1 + 1 全1组成
*/
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, n);
dp[0] = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j *j] + 1);
}
}
return dp[n];
}
}
class Solution {
/**
dp[i] 面值为i的零钱最少可以兑换的硬币数
不可达值设置成amount + 1
*/
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // 不可达值
dp[0] = 0;
for(int i = 0; i < dp.length; i++) {
for(int coin: coins) {
if(i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
else {
continue;
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
/**
不可达值设置成-1
*/
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, -1); // 不可达值
dp[0] = 0;
for(int i = 0; i < dp.length; i++) {
for(int coin: coins) {
if(i == coin) {
dp[i] = 1;
}
else if(i > coin) {
if(dp[i - coin] == -1) {
continue;
}
else {
if(dp[i] == -1) {
dp[i] = dp[i - coin] + 1;
}
else {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
}
}
return dp[amount];
}
}
class Solution {
/**
dp[i] 表示前i个字符的组合，可以被字典拼接成
boolean类型的数组
dp[s.len + 1]
dp[j] + substring(j, i) -- 在word里面
*/
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> map = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int i = 1; i < dp.length; i++) {
for(int j = 0; j < i; j++) {
if(dp[j] && map.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
class Solution {
/**
dp[i] 表示元素i结束的最长子序列
*/
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
for(int i = 1; i < dp.length; i++) {
for(int j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int maxlen = Integer.MIN_VALUE;
for(int i = 0; i < dp.length; i++) {
if(dp[i] > maxlen) {
maxlen = dp[i];
}
}
return maxlen;
}
}
class Solution {
/**
boolean dp[i] 前i个数字是否存在子集和为i
*/
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if(sum % 2 != 0) {
return false;
}
int mid = sum/2;
boolean[] dp = new boolean[mid + 1];
dp[0] = true;
for(int i = 1; i < nums.length; i++) {
for(int j = dp.length - 1; j >= nums[i - 1]; j--) {
if(dp[j - nums[i - 1]]) {
dp[j] = true;
}
}
}
return dp[mid];
}
}
二维动态规划
不同路径
class Solution {
/**
dp[i][j] 表示从start点走到(i, j)的位置，总共有多少条不同路径
dp[i][j] dp[i - 1][j] 向右 dp[i][j - 1] 向下
*/
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for(int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
class Solution {
/**
dp[i][j]表示从左上角到(i, j)位置的最小数字总和
dp[i][j] 只能由d[i - 1][j]向右， 或者d[i][j - 1]向下
dp[i - 1][j] + nums[i][j] dp[i][j - 1] + nums[i][j]
*/
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for(int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
}
}
return dp[m - 1][n - 1];
}
}
class Solution {
/**
dp[i] 以字符串的第i个位置的字母结尾的最长回文子串
不太理解
双指针法能写
判断是否回文子串 奇数 i 向两边扩散, 偶数i i+1 向两边扩散
*/
public String longestPalindrome(String s) {
String res = "";
for(int i = 0; i < s.length(); i++) {
String res1 = isPalindrome(s, i, i);
String res2 = isPalindrome(s, i, i + 1);
res = (res1.length() > res.length()) ? res1 : res;
res = (res2.length() > res.length()) ? res2 : res;
}
return res;
}
public String isPalindrome(String s, int l, int r) {
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return s.substring(l + 1, r);
}
}
class Solution {
/**
0 a b c d e
0 0 0 0 0 0 0
a 0 1 0 0 0 0
b 0 1 2 2 2 2
c 0 1 2 3 3 3
dp[i][j] text1以i结尾的字符串，和text2以j结尾的字符串，最长匹配到的公共子序列
i 和 j结尾的字符能匹配上
text1.charAt(i-1) == text2.charAt(j - 1) ? dp[i - 1][j - 1] + 1
不能匹配上 dp[i - 1][j], dp[i][j - 1]往前比较，取最大值
*/
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for(int i = 1; i <= text1.length(); i++) {
for(int j = 1; j <= text2.length(); j++) {
if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
class Solution {
/**
dp[i][j] 表示word1以i结尾的子串转换成word2以j结尾的子串需要的最少操作数
初始化 dp[0][j] = j
dp[i][0] = i
0 h o r s e
0 0 1 2 3 4 5
r 1 1
o 2
s 3
i和j处的字符不相等
dp[i][j] -- dp[i - 1][j] + 1 改i ? 增 or 删 or 替换
-- dp[i][j - 1] + 1 改j
-- dp[i - 1][j - 1] + 1 替换(i, j)
i和j处的字符不相等
*/
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for(int i = 1; i <= word1.length(); i++) {
dp[i][0] = i;
}
for(int j = 1; j <= word2.length(); j++) {
dp[0][j] = j;
}
for(int i = 1; i <= word1.length(); i++) {
for(int j = 1; j <= word2.length(); j++) {
if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[word1.length()][word2.length()];
}
}
原文地址：https://blog.csdn.net/qq_44072579/article/details/140220192
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！