首页 > 代码库 > 动态规划以及在leetcode中的应用
动态规划以及在leetcode中的应用
之前只是知道动态规划是通过组合子问题来解决原问题的,但是如何分析,如何应用一直都是一头雾水。最近在leetcode中发现有好几道题都可以用动态规划方法进行解决,就此做下笔录。
动态规划:应用于子问题重叠情况,原问题的多个子问题间可能含有相同的子子问题,当然,关于将原问题分解成子问题的思路,分治算法也是可行的,但是如果采用分治递归来解决就会出现一些问题。在重复的子问题的计算中,分治算法会忽略到重复问题,也就是说相同的问题,分治算法会计算多次,这样效率会很低。而动态规划算法会仔细安排求解顺序,对每个子问题只求解一次,并将结果保留下来,这样当遇到重复问题,只需查找保存结果,无需重新计算。
动态规划有两种等价的实现方法:
1.带备忘的自顶向下法。
2.自底向上法。
LeetCode题目---Decode Ways:
A message containing letters from A-Z
is being encoded to numbers using the following mapping:
‘A‘ -> 1‘B‘ -> 2...‘Z‘ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
分析:
边界条件:
1. 输入字符串长度为0时,则为0
2. 输入字符串的第一个数不能为0,若为0,则为0
根据例子我们可以知道问题可以分解成sum[i]=sum[i-1]+sum[i-2](i>1).
可以采用自底向上法的思想,有顺的将子问题有小到大进行求解。
代码如下:
public int numDecodings(String s) { if(0 == s.length()) return 0; if(s.charAt(0)==‘0‘) return 0; int []num = new int[s.length()];//记录遍历到字符串第i位置时的状态(该状态指的是编码的方法数) num[0] = 1; for(int i=1;i<s.length();i++){ if(s.charAt(i) != ‘0‘) num[i] = 1; String temp = s.substring(i-1, i+1); if(temp.charAt(0)==‘0‘) continue; if(Integer.parseInt(temp)>0&&Integer.parseInt(temp)<27){ if(1==i){ num[i]+=1; }else{ num[i]+=num[i-2]; } } } return num[s.length()-1]; }
当然leetcode中不只一道用到动态规划的思想,后续会再总结其他题目。
动态规划以及在leetcode中的应用