leetcode | go | 第600题 | 不含连续1的非负整数
- 开发
- 64
-
不含连续1的非负整数
go
解决思路
- 题解思路：（1）动态规划
- 完全二叉树
- 二叉树高度
- 动态规划：（1）为什么当前第 i 位为 1 的时候，ans 加上的是 dp[i+1] 呢，因为一共有 i+1 位数，相当于树的高度为 i+1（2）加上 dp[i+1]，以及设 pre=1 是什么含义呢？当前位可以为 0 或 1，相当于把当前位为 0 的满足条件的情况（即高度为 i+1 的满二叉树），全都加上了，然后当前位即为 1 了（3）当前位为 0 的情况处理完后，当前位只能为 1，前一位 pre 如果也是 1，那么此后的路径都是包含连续 1，所以直接 break（4）如果当前位只能为 0，那么设 pre 为 0（如果当前结点只包含一个左子结点，那么继续处理其左子结点） （5）i==0 时，为什么 ans 要 ++，因为考虑到最后一位了，前一位如果为 1，会在此之前 break，所以前一位为 0，最后一位只加上了为 0 的情况，在前一位为 0 时，当前位为 1 也符合条件，所以 ans++
相关问题
- 标签：动态规划
- 看了眼评论区，这道题目是数位 dp
- 现在能求出来，i 位数的不含连续 1 的非负整数个数，然后就是把 i 位数中 >n 的部分去掉吧
- 没想到我还真不会去掉
《女主对此感到厌烦》妚鹤_晋江文学城_【原创小说】
原文地址:https://blog.csdn.net/m0_54190747/article/details/135213992
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。
本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：https://www.suanlizi.com/kf/1739869218012270592.html
如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！
