class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[]f = new int[n+1];
f[0] = cost[0];
f[1] = cost[1];
for(int i = 2;i<n;i++){
f[i] = Math.min(f[i-1]+cost[i],f[i-2]+cost[i]);
}
return Math.min(f[n-1],f[n-2]);
}
}
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
for(int i = 2;i<n;i++){
cost[i] = Math.min(cost[i-1]+cost[i],cost[i-2]+cost[i]);
}
return Math.min(cost[n-1],cost[n-2]);
}
}
public class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n>1){
nums[1] = Math.max(nums[0],nums[1]);
}
for(int i = 2;i < n;i++){
nums[i] = Math.max(nums[i-1],nums[i-2]+nums[i]);
}
return nums[n-1];
}
}
public class Solution {
public int deleteAndEarn(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
int len = nums.length;
int max = nums[0];
for(int i = 0;i < len; i ++){
max = Math.max(max,nums[i]);
}
int[]count = new int[max+1];
for(int i = 0; i < len; i++){
count[nums[i]]++;
}
int dp[] = new int[max+1];
dp[1] = count[1]*1;
for(int i = 2;i <= max; i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+count[i]*i);
}
return dp[max];
}
}
矩阵类型
不同路径
题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
public class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[]dp = new int[n];
for(int i = 0; i < n; i ++){
dp[i] = 1;
}
int res = 1;
for(int i = 1; i < n; i ++){
for(int j = 0; j < i;j ++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
res =Math.max(res,dp[i]);
}
return res;
}
}
for(int i = 1; i < n; i ++){
for(int j = 0; j < i;j ++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
res =Math.max(res,dp[i]);
}
没有i-1的部分，（一般应该也是一维的dp吧）用0到n-1
**代码**：
public class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length();
int n2 = text2.length();
int [][]dp = new int[n1+1][n2+1];
int re = 0;
for(int i = 1;i <= n1; i++){
for(int j = 1;j<=n2;j++){
if(text2.charAt(j-1)==text1.charAt(i-1)){
dp[i][j] = dp[i-1][j-1]+1;
re = Math.max(re,dp[i][j]);
}
else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n1][n2];
}
}
public class Solution {
public static int numSquares(int n) {
int dp[] = new int[n+1];
int k = 1;
for(int i = 1;i <= n;i++){
if(i==kk){
dp[i] = 1;
k++;
}
else{
int k1 = 1;
dp[i] = dp[i-1]+1;
while(k1<k){
int j = i - k1k1;
dp[i] = Math.min(dp[i],dp[j]+1);
k1++;
}
}
}
return dp[n];
}
}
斐波那契数列
爬楼梯
问题： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路：（没想出来） 怎么爬到第5层？ 第一种：第四层爬1 第二种：第三层爬2 所以 f(5) = f(4)+f(3) 斐波那契数列！
我写的代码：
复杂度： 时间复杂度和空间复杂度都是 O(n) 优化： 由于这里的 f(x)只和 f(x−1)与 f(x−2)有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1) 不用数组存储之前的所有结果，只用两个变量临时存储前两个答案 0 1 p q r 0 1 1 1 1 2 1 2 3 2 3 5 优化后的代码：
最小花费爬楼梯
题目： 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。
我的思路： 爬到第n层一共花费f(n) f(n) = min [ f{n-1)+cost(n) , f(n-2)+cost(n) ] f(0) = cost(0) f(1) = cost(1) 要求的是cost(n) ⚠但是题目给出的cost数组下标是0-n-1，一共n个数，没有n这个下标，所以最终的答案要另外计算 我的代码：
通过了！但是依然可以按上面那题的方法优化空间复杂度，不存储过程的变量 进一步：可以直接用题目中的数组cost来存储
打家劫舍
题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
我的思路： dp[i] : 到下标i为止，能偷到的最多的钱 dp[i] = max( dp[i-1] , dp[i-2] + nums[i] ) dp[0] = nums[0] dp[1] = max( nums[0] , nums[1])
⚠要注意： 不是每一个数组长度都超过1，所以不是每个都有dp[1]，要先判断，不然会越界
优化：用题目给的数组存储dp 空间复杂度为O(1)
我的代码：（优化后）
删除并获得点数
题目：
给你一个整数数组 nums ，你可以对它进行一些操作。 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
我的思路：（看了一点提示） 转换成打家劫舍 第一次想到的把223334转换成494，但是样例通过了，其他的没通过，因为比如13虽然看上去相邻其实不相邻 所以又想到新开一个数组count[i]存储数字i出现的次数，这样可以看出来是否真的相邻 子问题dp[j] = max( dp[j-1] , dp[j-2] + count[i] * i 所以需要新开两个数组，i和j是分别遍历的
我的代码：（修改了几次之后通过了，但是时间空间复杂度都需要优化）
优化： 需要优化的点：
代码：
矩阵类型
不同路径
题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？
我的思路： ①用排列组合 但是通不过！！可能因为数太大了越界？或者是除法精度…… 所以！ ②还是用动态规划！ dp[i][j] = dp[i-1][j] + dp[i][j-1]
三角形最小路径和
题目：
给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
我的思路： 自顶向下，算出走到每一步的最小路径，最后比较最后一行得出最小的 ⚠ List的长度是 List.size() 二维的List取数 List.get(i).get(j)
我的代码：
优化： 从底下往上推，这样最后不用比较最后一行最小的，直接输出最顶上的一个就可以； 而且不用单独给最旁边的两列赋值，全部都可以用公式 定义dp数组的时候多定义一位，就不用单独给最后一行赋值（因为初值都是0，也可以用公式）
下降路径最小和
题目：
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
我的代码：（空间复杂度很大）
优化： 不用新建数组，直接在原来的上面改 （这样还有一个好处就是第一行直接就是原来的，不用特殊处理，遍历从第二行开始） 还有，题目说了n×n!!!!!!!
最大正方形
题目：
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
思路：（没有想到，看了提示才想到）
if(matrix[i][j] == '1'){ dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1; }
其中，dp(i, j) 是以 matrix(i, j) 为 右下角 的正方形的最大边长。
代码：
动态规划在字符串中的应用
最长回文子串
题目： 给你一个字符串 s，找到 s 中最长的回文子串 （有多个就输出第一个）
思路：（没想出来，看了提示dp的递推之后自己写的代码） 状态转移方程， dp[i][j] = dp[i + 1] [j - 1] && s[i] == s[j] 但是ij相邻的情况要特殊考虑 循环怎么写想了好久（不是一般的i循环里面j循环，是01，12，23，34，，，02，13，24，，，03，14，，，04）
代码：
单词拆分
思路：没想出来…… 主要是没想到用boolean的一维的dp，dp[i]来表示字符串s的前i个字符是否可以被拆分成字典中的单词！！！我一直在想用 dp[i][j] 表示s里的i-j位是否能被表示 状态转移方程： dp[i]=dp[j] && check(s[j..i−1]) 代码：
编辑距离 （好难的题）
思路：根本没思路
dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数；
dp[i-1][j-1] (表示替换)：word1的前i-1个字符已经变换到word2的前j-1个字符的次数，说明word1的前i-1个和word2的前j-1个字符已经完成操作；那么对于word1的第i个怎么变成word2的第j个呢？这两个字符都存在，那么只能是替换了；所以dp[i][j] = dp[i-1][j-1]+1; dp[i][j-1] (表示插入)：word1的前i个字符已经变换到word2的前j-1个字符的次数，当前word1的第i步字符已经用了，但是word2还差一个字符（因为当前只是处理了word2的前j-1个字符），那么插入一个字符就好了；所以dp[i][j] = dp[i][j-1]+1; dp[i-1][j] (表示删除)：word1的前i-1个字符已经变换到word2的前j个字符的次数，当前word1仅用了前i-1个字符就完成了到word2的前j个字符的操作，所以word1的第i个字符其实没啥用了，那么删除操作就好了；所以dp[i][j] = dp[i-1][j]+1; ⚠我自己写代码的时候漏掉了这个特殊的定义，代表word1为空的时候，需要增加n2次；word2为空的时候，需要删除n1次
代码：
两个字符串的最小ASCII删除和
题目：
给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
思路： 不用关心它内部究竟是怎么实现的，只要知道状态转移方程就好 ⚠对这个else的理解：
dp[i][j]代表s1前i项和s2前j项的最小ascii删除距离，如果最后两项不相等，一定会至少删除一项，但是这个时候不是直接比较哪个ascii小，因为不是删了一项就结束的，还要加上剩下的i-1项和j项的最小ascii距离。 代码：
不同的子序列
题目：
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
思路：（自己想的！困难题！） 秉持着不管过程，只想状态转移方程 画了个图：
一开始想的是这样的：
其实知道正经的应该改成dp[i][j] = dp[i-1][j-1]+dp[i][j-1],但是觉得如果最后一位不是那个字母的话上面那一行正上方的数和左边的数应该是一样的，想不通我的答案为什么不对。后来把rabbit的表列出来，发现不一定！有可能两个相同的字母挨着！
代码：
最长递增子序列
题目：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
思路：（没想出来，我想得很复杂……还是想得太多了，没有关注状态转移方程
dp[i] 的值代表 nums 以 nums[i]nums[i]nums[i] 结尾的最长子序列长度。（⚠这个很重要！不是前i个的最长子序列，而是以i结尾的！）
代码：
最长公共子序列
题目：
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
思路：（自己想的还是复杂了……） 现在做下来有两类题，一类的dp是从0开始到n，一类从0到n-1，主要是看
状态转移方程的递推是直接两层循环i，j然后用dp[i-1][j-1]，dp[i][j-1]，dp[i-1][j]算--------从0到n（循环从1开始，多出来的一个是为了i-1，j-1） 像这道题：
这里直接是dp[i][j-1] 和 dp[i-1][j]，是因为没有删除、替换啥啥的操作
状态转移方程这样：
public class Solution { public int longestCommonSubsequence(String text1, String text2) { int n1 = text1.length(); int n2 = text2.length(); int [][]dp = new int[n1+1][n2+1]; int re = 0; for(int i = 1;i <= n1; i++){ for(int j = 1;j<=n2;j++){ if(text2.charAt(j-1)==text1.charAt(i-1)){ dp[i][j] = dp[i-1][j-1]+1; re = Math.max(re,dp[i][j]); } else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); } } } return dp[n1][n2]; } }
public class Solution { public static int numSquares(int n) { int dp[] = new int[n+1]; int k = 1; for(int i = 1;i <= n;i++){ if(i==kk){ dp[i] = 1; k++; } else{ int k1 = 1; dp[i] = dp[i-1]+1; while(k1<k){ int j = i - k1k1; dp[i] = Math.min(dp[i],dp[j]+1); k1++; } } } return dp[n]; } }