最长连续递增子序列3

table及其下标的含义确定递推公式初始化dp数组确定遍历顺序举例推导dp数组

最少硬币数

考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j

coins[i]]

这种遍历顺序的意义是在计算找零过程中我们首先考虑金额的变化然后再考虑不同的硬币面额。

也就是说我们固定一个金额尝试使用不同的硬币面额来找零。

这样做的好处是可以利用之前已经计算出来的金额的最少硬币数快速得到当前金额的最优解。

由于金额是从小到大递增的所以我们在计算每个金额的最优解时可以利用前面较小金额的最优解已经被计算出来的特点。

遍历金额

这种遍历顺序的意义是在计算找零过程中我们首先考虑不同的硬币面额然后再考虑不同的金额。

也就是说我们固定一个硬币面额尝试在不同的金额下进行找零。

这样做的好处是可以保证我们将所有可能的硬币面额都考虑到并且在计算每个金额的最优解时可以利用之前已经计算出来的较小金额的最优解。

由于硬币面额是从小到大递增的所以我们在计算每个金额的最优解时可以利用之前较小硬币面额的最优解已经被计算出来的特点。

遍历硬币面额

dp[i]表示以nums[i]为结尾的最长连续递增序列的长度。

确定递推公式

我们将dp数组的所有元素初始化为1因为每个元素都可以作为一个单独的递增序列。

确定遍历顺序

Arrays.stream(dp).max().getAsInt();}

class

表示以第i个数字结尾的最长递增子序列的长度。

下标的含义dp[i]

确定递推公式

这里的i和j表示数组nums的索引。

具体来说i表示当前遍历到的元素的索引而j表示在i之前的元素的索引。

当我们遍历到第i个元素时我们需要寻找在i之前的元素中比nums[i]小的元素。

这样我们就可以利用这个小于nums[i]的元素来构成一个更长的递增子序列。

nums[j]时表示nums[i]比nums[j]大我们可以将以j结尾的最长递增子序列的长度加1然后与以i结尾的最长递增子序列的长度进行比较取较大的值作为以i结尾的最长递增子序列的长度。

也就是递推公式中的

dp[i]

初始时dp数组中的每个元素都设为1因为最短的递增子序列长度为1。

确定遍历顺序

外层循环遍历数组nums从左到右依次计算dp[i]的值。

内层循环遍历数组nums从数组开始到i的位置寻找前面的数字nums[j]是否小于nums[i]如果是则根据递推公式更新dp[i]的值。

举例推导dp数组

9此时没有比9小的元素所以以9结尾的最长递增子序列长度仍为1。

nums:

2此时在2之前有9和10两个元素都比2大所以以2结尾的最长递增子序列长度仍为1。

nums:

5此时在5之前有2和9两个元素其中2比5小所以以5结尾的最长递增子序列长度为dp[2]

nums:

3此时在3之前有2和5两个元素其中2比3小所以以3结尾的最长递增子序列长度为dp[2]

nums:

dp[i]表示从字符串的起始位置到第i个字符时的解码方法总数。

确定递推公式

dp[i-1]因为第i个字符自身可以作为一个解码方法如果第i个字符与前一个字符组成的两位数能够解码即与前一个字符组成的数字在1到26之间则dp[i]

则递推公式为dp[i]

如果第i个字符与前一个字符组成的两位数能够解码即与前一个字符组成的数字在1到26之间if

i)))

如果第1个字符与第2个字符组成的两位数为26能够解码为26所以dp[2]

dp[0]即dp[2]

如果第2个字符与第3个字符组成的两位数为26能够解码为26所以dp[3]

dp[1]即dp[3]

如果第i个字符与前一个字符组成的两位数能够解码即与前一个字符组成的数字在1到26之间if

i)))

这题就是62的改版所以复杂了很多还是建议看代码随想录动态规划——不同路径

动规五部曲

这条边有了障碍之后障碍之后包括障碍都是走不到的位置了所以障碍之后的dp[i]

下标(0,

}注意代码里for循环的终止条件一旦遇到obstacleGrid[i]

[0]

uniquePathsWithObstacles(int[][]

obstacleGrid)

int[m][n];//如果在起点或终点出现了障碍直接返回0if

(obstacleGrid[m

}至于118119我个人觉得并不合适使用动态规划的方式所以就不写了over~~