2015选择做导航网站,网站镜像做排名,网络营销公司主要做些什么,简述四大行业的网站推广方式文章目录题目描述思路 代码1. 动态规划做法2. DFS 做法二刷打卡第六天~继续加油#xff01; 题目描述
万物皆可爬楼梯.…和爬楼梯原理很像#xff0c;都是使用动态规划的做法来做~
思路 代码
1. 动态规划做法
初始化#xff1a;dp[0] 1, dp[1] …
文章目录题目描述思路 代码1. 动态规划做法2. DFS 做法二刷打卡第六天~继续加油 题目描述
万物皆可爬楼梯.…和爬楼梯原理很像都是使用动态规划的做法来做~
思路 代码
1. 动态规划做法
初始化dp[0] 1, dp[1] 1。dp[i] 代表 [0, i - 1] 的数字可翻译成的字符串种数dp[0] 无实际意义只是为了方便计算。状态转移方程第 i 个字符作为单个字符直接加到上一个字符的组合有 dp[i - 1] 种结果。 而和第 i - 1 个字符可组成字符则再加上 dp[i - 2] 种结果。
class Solution {public int translateNum(int num) {// 先转换成数组方便操作char[] nums String.valueOf(num).toCharArray();int count 0;// dp 做法类似跳台阶。// dp[i]从[1, i]的子串可行方法, dp[0] 不是实际值int[] dp new int[nums.length 1];dp[0] 1;dp[1] 1;for(int i 2; i nums.length; i) {// 1. 作为单个字符直接加上的情况dp[i] dp[i - 1];int temp (nums[i - 1 - 1] - 0) * 10 (nums[i - 1] - 0);// 2. 可以和前一个字符组合变成两个的情况if(temp 10 temp 25) {dp[i] dp[i - 2];}}return dp[nums.length];}
}2. DFS 做法
补一个当时的做法这道题用 DFS 的思路也很好理解设定一个全局变量在 DFS 的过程中不断维护即可
class Solution {int count 0;char[] nums;public int translateNum(int num) {// 先转换成数组方便操作nums String.valueOf(num).toCharArray();dfs(0, nums.length - 1);return count;}public void dfs(int start, int end) {if(start end) {count;return;}dfs(start 1, end);if(start 1 nums.length (nums[start] - 0) * 10 (nums[start 1] - 0) 26 (nums[start] - 0) * 10 (nums[start 1] - 0) 10) {dfs(start 2, end);}}
}二刷
class Solution {public int translateNum(int num) {char[] arr ( num).toCharArray();int[] dp new int[arr.length 1];dp[0] 1;dp[1] 1;for(int i 2; i arr.length; i) {dp[i] dp[i - 1];int temp (arr[i - 2] - 0) * 10 (arr[i - 1] - 0);if(temp 9 temp 26) {dp[i] dp[i - 2];}}return dp[arr.length];}
}
