• 售前

  • 售后

热门帖子
入门百科

动态规划练习——规定1和A对应、2和B对应、3和C对应…那么

[复制链接]
xinting_6ym 显示全部楼层 发表于 2022-1-15 18:40:00 |阅读模式 打印 上一主题 下一主题
题目

规定1和A对应、2和B对应、3和C对应…那么一个数字字符串比如"111”就可以转化为:'AAA"、 “KA"和"AK”。给定一个只有数字字符组成的字符串str,返回有多少种转化结果
动态规划关键在于暴力解是否能够顺利写出来,也就是说把尝试过程想清楚后,再将其替换成结构化的缓存结构,所以尝试过程很重要。这个题的暴力解请看这篇博客——暴力递归——从左往右的尝试模型1,Facebook面试真题,。博主多次讲到过,改动态规划的过程跟原题意已经没有关系了,也就是说跟原题意已经解耦了。
所以,如果你看懂了暴力尝试的方法后,我们就直接在此基础上改动态规划:
[code]public static int dpways1(String s) {                if(s==null || s.length()==0) {                        return 0;                }                char[] str=s.toCharArray();                int N=str.length;                int[] dp=new int[N+1];                dp[N]=1;                for(int i=N-1; i>=0; i--) {                        if(str=='0') {                                dp=0;                        }else if(str=='1') {                                dp=dp[i+1];                                if(i+1

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作