动态规划（DynamicProgramming）-创新互联
斐波那契额数列
1.爬楼梯
分享文章：动态规划（DynamicProgramming）-创新互联
网站URL：http://hbruida.cn/article/coiech.html
// 上楼梯
public class Ti0070 {// dp[i] = dp[i - 1] + dp[i - 2]
public int climbStairs(int n) {if (n<= 2) return n;
int[] dp = new int[n + 1];
dp[1]= 1; dp[2] = 2;
for (int i = 3; i<= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {Assert.check(2 == new Ti0070().climbStairs(2));
Assert.check(3 == new Ti0070().climbStairs(3));
}
}扩展：一次可以爬1,2,3,…m台阶
为普兰等地区用户提供了全套网页设计制作服务，及普兰网站建设行业解决方案。主营业务为成都网站建设、网站设计、普兰网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
public class Ti0070_1 {public int climbStairs(int n) {int m = 2; // 1, 2 一次可跳
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i<= n; i++) {for (int j = 1; j<= m; j++) {if (i - j >= 0) dp[i] += dp[i - j];
else break;
}
}
return dp[n];
}
public static void main(String[] args) {Assert.check(2 == new Ti0070().climbStairs(2));
Assert.check(3 == new Ti0070().climbStairs(3));
}
}public class Ti0198 {public int rob(int[] nums) {int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i<= nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.length];
}
public static void main(String[] args) {Assert.check(4 == new Ti0198().rob(new int[]{1, 2, 3, 1}));
Assert.check(12 == new Ti0198().rob(new int[]{2, 7, 9, 3, 1}));
}
}public class Ti0213 {public int rob(int[] nums) {if (nums.length == 1) return nums[0];
return Math.max(subRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
subRob(Arrays.copyOfRange(nums, 1, nums.length)));
}
public int subRob(int[] nums) {int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i<= nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.length];
}
public static void main(String[] args) {Assert.check(3 == new Ti0213().rob(new int[]{2, 3, 2}));
Assert.check(4 == new Ti0213().rob(new int[]{1, 2, 3, 1}));
Assert.check(3 == new Ti0213().rob(new int[]{1, 2, 3}));
}
}题述：有N个信 和 信封，它们被打乱，求错误装信方式的数量。
5.母牛生产程序员代码面试指南 - P181
题述：农场中成熟的母牛每年都会生 1 头小母牛，且永生。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。
public class GuideP181 {public int getCowCount(int year) {int[] dp = new int[year + 1];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i<= year; i++) {dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[year];
}
public static void main(String[] args) {Assert.check(21 == new GuideP181().getCowCount(7));
}
}public class Ti0064 {public int minPathSum(int[][] grid) {int m = grid.length, 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] = grid[i][0] + dp[i - 1][0];
}
for (int i = 1; i< n; i++) {dp[0][i] = grid[0][i] + dp[0][i - 1];
}
for (int i = 1; i< m; i++) {for (int j = 1; j< n; j++) {dp[i][j] = grid[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {Assert.check(7 == new Ti0064().minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
Assert.check(12 == new Ti0064().minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
}
}public class Ti0062 {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];
Arrays.fill(dp[0], 1);
for (int i = 1; i< m; i++) {dp[i][0] = 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];
}
public static void main(String[] args) {Assert.check(28 == new Ti0062().uniquePaths(3, 7));
Assert.check(3 == new Ti0062().uniquePaths(3, 2));
Assert.check(6 == new Ti0062().uniquePaths(3, 3));
}
}public class Ti0303 {public static void main(String[] args) {NumArray numArray = new NumArray(new int[]{-2, 0, 3, -5, 2, -1});
Assert.check(1 == numArray.sumRange(0, 2));
Assert.check(-1 == numArray.sumRange(2, 5));
Assert.check(-3 == numArray.sumRange(0, 5));
}
}
class NumArray {private int[] sums;
public NumArray(int[] nums) {sums = new int[nums.length];
if (nums.length == 0) return;
sums[0] = nums[0];
for (int i = 1; i< nums.length; i++) {sums[i] = sums[i - 1] + nums[i];
}
}
public int sumRange(int left, int right) {if (left == 0) return sums[right];
return sums[right] - sums[left - 1];
}
}public class Ti0413 {public int numberOfArithmeticSlices(int[] nums) {if (nums.length<= 2) return 0;
int res = 0;
int[] dp = new int[nums.length];
for (int i = 2; i< nums.length; i++) {if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {dp[i] = dp[i - 1] + 1;
res += dp[i];
}
}
return res;
}
public static void main(String[] args) {Assert.check(3 == new Ti0413().numberOfArithmeticSlices(new int[]{1, 2, 3, 4}));
}
}public class Ti0343 {public int integerBreak(int n) {// 存放乘积大值
int[] dp = new int[n + 1];
// i-被拆分数
for (int i = 2; i<= n; i++) {// j-拆分出1,2,...i-1, 但一半就行, 其余都是相反的. 1*3 3*1...
for (int j = 1; j< i / 2 + 1; j++) {dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
public static void main(String[] args) {Assert.check(1 == new Ti0343().integerBreak(2));
Assert.check(36 == new Ti0343().integerBreak(10));
}
}public class Ti0279 {public int numSquares(int n) {int[] dp = new int[n + 1];
for (int i = 1; i<= n; i++) {dp[i] = i;
for (int j = 1; i - j * j >= 0; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
public static void main(String[] args) {Assert.check(3 == new Ti0279().numSquares(12));
Assert.check(2 == new Ti0279().numSquares(13));
}
}public class Ti0091 {public int numDecodings(String s) {int n = s.length();
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i<= n; ++i) {if (s.charAt(i - 1) != '0') {f[i] += f[i - 1];
}
if (i >1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0')<= 26)) {f[i] += f[i - 2];
}
}
return f[n];
}
public static void main(String[] args) {Assert.check(2 == new Ti0091().numDecodings("12"));
Assert.check(3 == new Ti0091().numDecodings("226"));
Assert.check(0 == new Ti0091().numDecodings("06"));
}
}public class Ti0300 {public int lengthOfLIS(int[] nums) {int res = 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
for (int i = 0; i< nums.length; i++) {for (int j = 0; j< i; j++) {if (nums[i] >nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
for (int k : dp) {if (k >res) res = k;
}
return res;
}
public static void main(String[] args) {Assert.check(4 == new Ti0300().lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
Assert.check(4 == new Ti0300().lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
Assert.check(1 == new Ti0300().lengthOfLIS(new int[]{7, 7, 7, 7, 7, 7, 7}));
}
}public class Ti0646 {public int findLongestChain(int[][] pairs) {Arrays.sort(pairs, Comparator.comparingInt(o ->o[0]));
int[] dp = new int[pairs.length];
Arrays.fill(dp, 1);
for (int i = 0; i< dp.length; i++) {for (int j = 0; j< i; j++) {if (pairs[j][1]< pairs[i][0]) {dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int res = 0;
for (int k : dp) {if (k >res) res = k;
}
return dp[pairs.length - 1];
}
public static void main(String[] args) {Assert.check(2 == new Ti0646().findLongestChain(new int[][]{{1, 2}, {2, 3}, {3, 4}}));
}
}public class Ti0376 {public int wiggleMaxLength(int[] nums) {int n = nums.length;
if (n< 2) {return n;
}
int up = 1, down = 1;
for (int i = 1; i< n; i++) {if (nums[i] >nums[i - 1]) {up = down + 1;
} else if (nums[i]< nums[i - 1]) {down = up + 1;
}
}
return Math.max(up, down);
}
public static void main(String[] args) {Assert.check(6 == new Ti0376().wiggleMaxLength(new int[]{1, 7, 4, 9, 2, 5}));
Assert.check(7 == new Ti0376().wiggleMaxLength(new int[]{1, 17, 5, 10, 13, 15, 10, 5, 16, 8}));
}
}public class Ti1143 {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i<= m; i++) {char c1 = text1.charAt(i - 1);
for (int j = 1; j<= n; j++) {char c2 = text2.charAt(j - 1);
if (c1 == c2) {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[m][n];
}
public static void main(String[] args) {Assert.check(3 == new Ti1143().longestCommonSubsequence("abcde", "ace"));
Assert.check(3 == new Ti1143().longestCommonSubsequence("abc", "abc"));
Assert.check(0 == new Ti1143().longestCommonSubsequence("abc", "def"));
}
}…待续
0-1背包 1.划分数组为和相等的两部分 2.改变一组数的正负号使得它们的和为一给定数 3.01字符串构成最多的字符串 4.找零钱的最少硬币数 5.找零钱的硬币数组合 6.字符串按单词列表分割 7.组合总和 股票交易 1.需要冷却的股票交易 2.需要交易费用的股票交易 3.只能进行两次的股票交易 4.只能进行k次的股票交易 字符串编辑 1.删除两个字符串的字符使它们相等 2.编辑距离 3.复制粘贴字符你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享文章：动态规划（DynamicProgramming）-创新互联
网站URL：http://hbruida.cn/article/coiech.html
